Geodesic
Vertex Bisection is Hard, too
Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 119-131.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00179
Keywords: linear graph layout, vertex bisection, hardness 
@article{JGAA_2009_13_2_a2,
     author = {Ulrik Brandes and Daniel Fleischer},
     title = {Vertex {Bisection} is {Hard,} too},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {119--131},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2009},
     doi = {10.7155/jgaa.00179},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00179/}
}
TY  - JOUR
AU  - Ulrik Brandes
AU  - Daniel Fleischer
TI  - Vertex Bisection is Hard, too
JO  - Journal of Graph Algorithms and Applications
PY  - 2009
SP  - 119
EP  - 131
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00179/
DO  - 10.7155/jgaa.00179
LA  - en
ID  - JGAA_2009_13_2_a2
ER  - 
%0 Journal Article
%A Ulrik Brandes
%A Daniel Fleischer
%T Vertex Bisection is Hard, too
%J Journal of Graph Algorithms and Applications
%D 2009
%P 119-131
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00179/
%R 10.7155/jgaa.00179
%G en
%F JGAA_2009_13_2_a2
Ulrik Brandes; Daniel Fleischer. Vertex Bisection is Hard, too. Journal of Graph Algorithms and Applications, Tome 13 (2009) no. 2, pp. 119-131. doi : 10.7155/jgaa.00179. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00179/

Cité par Sources :