Graph Bipartization Problem with Applications to Via Minimization in VLSI Design
Abstract
The bipartization problem for a graph G asks for finding a subset S of V(G) such that the induced subgraph G[S] is bipartite and |S| is maximized. This problem has significant applications in the via minimization of VLSI design. The problem has been proved NP-complete and the fixed parameter solvability has been known in the literature. This paper presents several polynomial-time algorithms for special graph families, such as split graphs, co-bipartite graphs, chordal graphs, and permutation graphs.
Supported by National Key R&D Program of China (2019YFB2101604).
Communicated by Yong Zhang
Remember to check out the Most Cited Articles! |
---|
Check out these Handbooks in Computer Science |