Vertex Bisection is Hard, too

Authors

  • Ulrik Brandes
  • Daniel Fleischer

DOI:

https://doi.org/10.7155/jgaa.00179

Keywords:

linear graph layout , vertex bisection , hardness

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.

Downloads

Download data is not yet available.

Downloads

Published

2009-02-01

How to Cite

Brandes, U., & Fleischer, D. (2009). Vertex Bisection is Hard, too. Journal of Graph Algorithms and Applications, 13(2), 119–131. https://doi.org/10.7155/jgaa.00179

Issue

Section

Articles

Categories