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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2012032/
[1] Graph Theory. Springer-Verlag, Berlin (2008). | MR | Zbl
and ,[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] A survey of graph layout problems. ACM Comput. Surveys 34 (2002) 313-356.
, and ,[5] A survey: recent results, conjectures, and open problems in labeling graphs. J. Graph Theory 13 (1989) 491-504. | MR | Zbl
,[6] Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979). | MR | Zbl
and ,[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] A degree sequence method for the cutwidth problem of graphs. Appl. Math. J. Chinese Univ. Ser. B 17(2) (2002) 125-134. | MR | Zbl
, and ,[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] The cutwidth problem for graphs. Appl. Math. J. Chinese Univ. Ser. A 10 (3) (1995) 339-348. | MR | Zbl
and ,[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] Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. Lect. Notes Comput. Sci. 1017 (1995) 252-264. | MR
, and ,[13] The bandwidth problem: critical subgraphs and the solution for caterpillars. Annal. Discrete Math. 16 (1982) 281-286. | MR | Zbl
and ,[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 :