Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00179 Vertex Bisection is Hard, too Ulrik Brandes and Daniel Fleischer 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.
|
Accepted: February 2009. Published: April 2009. Submitted: December 2005. Revised: April 2007. Final: February 2009. Reviewed: April 2006. Communicated by Susanne Albers |
Journal of Graph Algorithms and Applications |