Voir la notice de l'article provenant de la source Numdam
The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.
@article{ITA_2013__47_2_181_0,
author = {Lin, Lan and Lin, Yixun},
title = {Cutwidth of iterated caterpillars},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {181--193},
publisher = {EDP-Sciences},
volume = {47},
number = {2},
year = {2013},
doi = {10.1051/ita/2012032},
mrnumber = {3072317},
zbl = {1266.05140},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2012032/}
}
TY - JOUR AU - Lin, Lan AU - Lin, Yixun TI - Cutwidth of iterated caterpillars JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2013 SP - 181 EP - 193 VL - 47 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2012032/ DO - 10.1051/ita/2012032 LA - en ID - ITA_2013__47_2_181_0 ER -
%0 Journal Article %A Lin, Lan %A Lin, Yixun %T Cutwidth of iterated caterpillars %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 181-193 %V 47 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2012032/ %R 10.1051/ita/2012032 %G en %F ITA_2013__47_2_181_0
Lin, Lan; Lin, Yixun. Cutwidth of iterated caterpillars. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 2, pp. 181-193. doi: 10.1051/ita/2012032
Cité par Sources :