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.
Mots clés : circuit layout design, graph labeling, cutwidth, caterpillar, iterated caterpillar
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita/2012032/
[1] and , Graph Theory. Springer-Verlag, Berlin (2008). | MR | Zbl
[2] , Labelings of graphs, edited by L.W. Beineke and R.J. Wilson. Selected Topics in Graph Theory 3 (1988) 151-168. | MR | Zbl
[3] , On the cutwidth and topological bandwidth of a tree. SIAM J. Algbr. Discrete Methods 6 (1985) 268-277. | MR | Zbl
[4] , and , A survey of graph layout problems. ACM Comput. Surveys 34 (2002) 313-356.
[5] , A survey: recent results, conjectures, and open problems in labeling graphs. J. Graph Theory 13 (1989) 491-504. | MR | Zbl
[6] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979). | MR | Zbl
[7] , Upper and lower bounds for the min-cut linear arrangement of trees. SIAM J. Algbr. Discrete Methods 3 (1982) 99-113. | MR | Zbl
[8] , and , A degree sequence method for the cutwidth problem of graphs. Appl. Math. J. Chinese Univ. Ser. B 17(2) (2002) 125-134. | MR | Zbl
[9] , The cutwidth of trees with diameter at most 4. Appl. Math. J. Chinese Univ. Ser. B 18(3) (2003) 361-368. | MR | Zbl
[10] and , The cutwidth problem for graphs. Appl. Math. J. Chinese Univ. Ser. A 10 (3) (1995) 339-348. | MR | Zbl
[11] , The bandwidth minimization problem for caterpipals with hair length 3 is NP-complete. SIAM J. Algbr. Discrete Methods 7 (1986) 505-512. | MR | Zbl
[12] , and , Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. Lect. Notes Comput. Sci. 1017 (1995) 252-264. | MR
[13] and , The bandwidth problem: critical subgraphs and the solution for caterpillars. Annal. Discrete Math. 16 (1982) 281-286. | MR | Zbl
[14] , Cutwidth of the r-dimensional mesh of d-ary trees. RAIRO Theor. Inform. Appl. 34 (2000) 515-519. | EuDML | Numdam | MR | Zbl
[15] , A polynomial algorithm for the min-cut arrangement of trees. J. ACM 32 (1985) 950-989. | MR | Zbl
Cité par Sources :
