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.