# Graph Bipartization and Via Minimization.

 dc.contributor.author Choi, Hyeong-Ah en_US dc.contributor.author Nakajima, Kazuo en_US dc.contributor.author Rim, Chong S. en_US dc.date.accessioned 2007-05-23T09:40:02Z dc.date.available 2007-05-23T09:40:02Z dc.date.issued 1987 en_US dc.identifier.uri http://hdl.handle.net/1903/4706 dc.description.abstract The 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.extent 865233 bytes dc.format.mimetype application/pdf dc.language.iso en_US en_US dc.relation.ispartofseries ISR; TR 1987-203 en_US dc.title Graph Bipartization and Via Minimization. en_US dc.type Technical Report en_US dc.contributor.department ISR en_US
﻿