Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00179
Vertex Bisection is Hard, too
Vol. 13, no. 2, pp. 119-131, 2009. Concise paper.
Abstract We settle an open problem mentioned in Diaz, Petit, and Serna: A survey of graph layout problems (ACM Computing Surveys 34:313-356, 2002). Of eight objectives considered in that survey, only the complexity status of minimum vertex bisection is listed as unknown. We show that both minimum and maximum vertex bisection are NP-hard, but polynomially solvable on special graph classes such as hypercubes and trees.
Submitted: December 2005.
Reviewed: April 2006.
Revised: April 2007.
Accepted: February 2009.
Final: February 2009.
Published: April 2009.
Communicated by Susanne Albers
article (PDF)
BibTeX