Show simple item record

Graph Bipartization and Via Minimization.

dc.contributor.authorChoi, Hyeong-Ahen_US
dc.contributor.authorNakajima, Kazuoen_US
dc.contributor.authorRim, Chong S.en_US
dc.date.accessioned2007-05-23T09:40:02Z
dc.date.available2007-05-23T09:40:02Z
dc.date.issued1987en_US
dc.identifier.urihttp://hdl.handle.net/1903/4706
dc.description.abstractThe vertex- (resp., edge-) deletion graph bipartization problem is the problem of deleting a set of vertices (resp., edges) from a graph so as to make the remaining graph bipartite. In this paper, we first show that the vertex-deletion graph bipartization problem has a solution of size k or less if and only if the edge- deletion graph bipartization problem has a solution of size k or less, when the maximum vertex degree is limited to three. This immediately implies that (1) the vertex-deletion graph bipartization problem is NP-complete for cubic graphs, and (2) the minimum vertex-deletion graph bipartization problem is solvable in polynomial time for planar graphs when the maximum vertex degree is limited to three. We then prove that the vertex- deletion graph bipartization problem is NP-complete for planar graphs when the maximum vertex degree exceeds three. Using this result, we finally show that the via minimization problem, which arises in the design of integrated circuits and printed circuit boards, is NP-complete even when the maximum "junction" degree is limited to four.en_US
dc.format.extent865233 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1987-203en_US
dc.titleGraph Bipartization and Via Minimization.en_US
dc.typeTechnical Reporten_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record