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
|
Journal Supporters
|