Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are satisfied concurrently, and the overall cost is approximately minimized.

We provide both serial and parallel implementation as well as develop several heuristics used to improve the quality of the solution and reduce running time. We provide computational results on two sets of well-known benchmarks and show that, with a certain set of heuristics, our new algorithms perform extremely well compared with other integer-programming models.

In 1956, Ryser gave a necessary and sufficient condition for a partial Latin rectangle to be completable to a Latin square. In 1990, Hilton and Johnson showed that Ryser’s condition could be reformulated in terms of Hall’s Condition for partial Latin squares. Thus, Ryser’s Theorem can be interpreted as saying that any partial Latin rectangle \( R \) can be completed if and only if \( R \) satisfies Hall’s Condition for partial Latin squares.

We define Hall’s Condition for partial Sudoku squares and show that Hall’s Condition for partial Sudoku squares gives a criterion for the completion of partial Sudoku rectangles that is both necessary and sufficient. In the particular case where \( n = pq \), \( p \mid r \), \( q \mid s \), the result is especially simple, as we show that any \( r \times s \) partial \((p, q)\)-Sudoku rectangle can be completed (no further condition being necessary).

Let \( G \) be a \((p, q)\)-graph. Suppose an edge labeling of \( G \) given by \( f: E(G) \to \{1, 2, \ldots, q\} \) is a bijective function. For a vertex \( v \in V(G) \), the induced vertex labeling of \( G \) is a function \( f^*(V) = \sum f(uv) \) for all \( uv \in E(G) \). We say \( f^*(V) \) is the vertex sum of \( V \). If, for all \( v \in V(G) \), the vertex sums are equal to a constant (mod \( k \)) where \( k \geq 2 \), then we say \( G \) admits a Mod(\( k \))-edge-magic labeling, and \( G \) is called a Mod(\( k \))-edge-magic graph. In this paper, we show that (i) all maximal outerplanar graphs (or MOPs) are Mod(\( 2 \))-EM, and (ii) many Mod(\( 3 \))-EM labelings of MOPs can be constructed (a) by adding new vertices to a MOP of smaller size, or (b) by taking the edge-gluing of two MOPs of smaller size, with a known Mod(\( 3 \))-EM labeling. These provide us with infinitely many Mod(\( 3 \))-EM MOPs. We conjecture that all MOPs are Mod(\( 3 \))-EM.

Let \(g(n, k)\) be the maximum number of colors for the vertices of the cube graph \(Q_n\), such that each subcube \(Q_k\) contains all colors. Some exact values of \(g(n, k)\) are determined.

Let \( G \) be a connected graph and let \( U \) be a set of vertices in \( G \). A \({minimal \; U -tree}\) is a subtree \( T \) of \( G \) that contains \( U \) and has the property that every vertex of \( V(T) – U \) is a cut-vertex of \( \langle V(T) \rangle \). The \({monophonic\; interval}\) of \( U \) is the collection of all vertices of \( G \) that lie on some minimal \( U \)-tree. A set \( S \) of vertices of \( G \) is \( m_k \)-\({convex}\) if it contains the monophonic interval of every \( k \)-subset \( U \) of vertices of \( S \). Thus \( S \) is \( m_2 \)-convex if and only if it is \( m \)-convex.

In this paper, we consider three local convexity properties with respect to \( m_3 \)-convexity and characterize the graphs having either property.

Let \( G \) and \( H \) be graphs on \( n+2 \) vertices \( \{u_1, u_2, \ldots, u_n, x, y\} \) such that \( G – u_i \cong H – u_i \), for \( i = 1, 2, \ldots, n \). Recently, Ramachandran, Monikandan, and Balakumar have shown in a sequence of two papers that if \( n \geq 9 \), then \( |\varepsilon(H) – \varepsilon(G)| \leq 1 \). In this paper, we present a simpler proof of their theorem, using a counting lemma.

We answer in the affirmative a question posed by Al-Addasi and Al-Ezeh in 2008 on the existence of symmetric diametrical bipartite graphs of diameter 4. Bipartite symmetric diametrical graphs are called \( S \)-graphs by some authors, and diametrical graphs have also been studied by other authors using different terminology, such as self-centered unique eccentric point graphs. We include a brief survey of some of this literature and note that the existence question was also answered by Berman and Kotzig in a 1980 paper, along with a study of different isomorphism classes of these graphs using a \( (1,-1) \)-matrix representation which includes the well-known Hadamard matrices. Our presentation focuses on a neighborhood characterization of \( S \)-graphs, and we conclude our survey with a beautiful version of this characterization known to Janakiraman.

The achromatic number for a graph \( G = (V, E) \) is the largest integer \( m \) such that there is a partition of \( V \) into disjoint independent sets \( (V_1, \ldots, V_m) \) such that for each pair of distinct sets \( V_i, V_j \), \( V_i \cup V_j \) is not an independent set in \( G \). In this paper, we present an \( O(1) \)-approximation algorithm to determine the achromatic number of circulant graphs \( G(n; \pm\{1, 2\}) \) and \( G(n; \pm\{1, 2, 3\}) \).

Let \( G = (V, E) \) be a graph with vertex set \( V \) and edge set \( E \). Let \( diam(G) \) denote the diameter of \( G \) and \( d(u, v) \) denote the distance between the vertices \( u \) and \( v \) in \( G \). An antipodal labeling of \( G \) with diameter \( d \) is a function \( f \) that assigns to each vertex \( u \) a positive integer \( f(u) \), such that \( d(u, v) + |f(u) – f(v)| \geq d \), for all \( u, v \in V \). The span of an antipodal labeling \( f \) is \( \max\{|f(u) – f(v)| : u, v \in V(G)\} \). The antipodal number for \( G \), denoted by \( an(G) \), is the minimum span of all antipodal labelings of \( G \). Determining the antipodal number of a graph \( G \) is an NP-complete problem. In this paper, we determine the antipodal number of certain graphs with diameter equal to \( 3 \) and \( 4 \).

A radio labeling of a connected graph \( G \) is an injection \( f \) from the vertices of \( G \) to the natural numbers such that \( d(u, v) + |f(u) – f(v)| \geq 1 + \operatorname{diam}(G) \) for every pair of distinct vertices \( u \) and \( v \) of \( G \). The radio number of \( f \), denoted \( rn(f) \), is the maximum number assigned to any vertex of \( G \). The radio number of \( G \), denoted \( rn(G) \), is the minimum value of \( rn(f) \) taken over all labelings \( f \) of \( G \). In this paper, we determine bounds for the radio number of the hexagonal mesh.