Geodesic
NP-Completeness of Minimal Width Unordered Tree Layout
Journal of Graph Algorithms and Applications, Tome 8 (2004) no. 3, pp. 295-312.

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

Tree layout has received considerable attention because of its practical importance. Arguably the most common drawing convention is the (ordered) layered tree convention for rooted trees in which the layout is required to preserve the relative order of a node's children. However, in some applications preserving the ordering of children is not important, and considerably more compact layout can be achieved if this requirement is dropped. Here we introduce the unordered layered tree drawing convention for binary rooted trees and show that determining a minimal width drawing for this convention is NP-complete. 
@article{JGAA_2004_8_3_a2,
     author = {Kim Marriott and Peter Stuckey},
     title = {NP-Completeness of {Minimal} {Width} {Unordered} {Tree} {Layout}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {295--312},
     publisher = {mathdoc},
     volume = {8},
     number = {3},
     year = {2004},
     doi = {10.7155/jgaa.00093},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00093/}
}
TY  - JOUR
AU  - Kim Marriott
AU  - Peter Stuckey
TI  - NP-Completeness of Minimal Width Unordered Tree Layout
JO  - Journal of Graph Algorithms and Applications
PY  - 2004
SP  - 295
EP  - 312
VL  - 8
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00093/
DO  - 10.7155/jgaa.00093
LA  - en
ID  - JGAA_2004_8_3_a2
ER  - 
%0 Journal Article
%A Kim Marriott
%A Peter Stuckey
%T NP-Completeness of Minimal Width Unordered Tree Layout
%J Journal of Graph Algorithms and Applications
%D 2004
%P 295-312
%V 8
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00093/
%R 10.7155/jgaa.00093
%G en
%F JGAA_2004_8_3_a2
Kim Marriott; Peter Stuckey. NP-Completeness of Minimal Width Unordered Tree Layout. Journal of Graph Algorithms and Applications, Tome 8 (2004) no. 3, pp. 295-312. doi : 10.7155/jgaa.00093. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00093/

Cité par Sources :