Cutwidth of iterated caterpillars

Lan Lin; Yixun Lin

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 2, page 181-193
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Lin, Lan, and Lin, Yixun. "Cutwidth of iterated caterpillars." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.2 (2013): 181-193. <http://eudml.org/doc/273025>.

@article{Lin2013,
abstract = {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.},
author = {Lin, Lan, Lin, Yixun},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {circuit layout design; graph labeling; cutwidth; caterpillar; iterated caterpillar},
language = {eng},
number = {2},
pages = {181-193},
publisher = {EDP-Sciences},
title = {Cutwidth of iterated caterpillars},
url = {http://eudml.org/doc/273025},
volume = {47},
year = {2013},
}

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
PB - EDP-Sciences
VL - 47
IS - 2
SP - 181
EP - 193
AB - 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.
LA - eng
KW - circuit layout design; graph labeling; cutwidth; caterpillar; iterated caterpillar
UR - http://eudml.org/doc/273025
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory. Springer-Verlag, Berlin (2008). Zbl1134.05001MR2368647
  2. [2] F.R.K. Chung, Labelings of graphs, edited by L.W. Beineke and R.J. Wilson. Selected Topics in Graph Theory3 (1988) 151–168. Zbl0656.05058MR1205400
  3. [3] F.R.K. Chung, On the cutwidth and topological bandwidth of a tree. SIAM J. Algbr. Discrete Methods6 (1985) 268–277. Zbl0565.05019MR778007
  4. [4] J. Diaz, J. Petit and M. Serna, A survey of graph layout problems. ACM Comput. Surveys34 (2002) 313–356. 
  5. [5] J.A. Gallian, A survey: recent results, conjectures, and open problems in labeling graphs. J. Graph Theory13 (1989) 491–504. Zbl0681.05064MR1010582
  6. [6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979). Zbl0411.68039MR519066
  7. [7] T. Lengauer, Upper and lower bounds for the min-cut linear arrangement of trees. SIAM J. Algbr. Discrete Methods3 (1982) 99–113. Zbl0489.68060MR644961
  8. [8] Y. Lin, X. Li and A. Yang, A degree sequence method for the cutwidth problem of graphs. Appl. Math. J. Chinese Univ. Ser. B 17(2) (2002) 125–134. Zbl1004.05052MR1904908
  9. [9] Y. Lin, The cutwidth of trees with diameter at most 4. Appl. Math. J. Chinese Univ. Ser. B 18(3) (2003) 361–368. Zbl1040.05025MR2004690
  10. [10] H. Liu and J. Yuan, The cutwidth problem for graphs. Appl. Math. J. Chinese Univ. Ser. A 10 (3) (1995) 339–348. Zbl0839.05082MR1361048
  11. [11] B. Monien, The bandwidth minimization problem for caterpipals with hair length 3 is NP-complete. SIAM J. Algbr. Discrete Methods7 (1986) 505–512. Zbl0624.68059MR857587
  12. [12] J. Rolin, O. Sykora and I. Vrt’o, Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. Lect. Notes Comput. Sci.1017 (1995) 252–264. MR1400027
  13. [13] M. M. Syslo and J. Zak, The bandwidth problem: critical subgraphs and the solution for caterpillars. Annal. Discrete Math.16 (1982) 281–286. Zbl0494.05058MR686313
  14. [14] I. Vrt'o, Cutwidth of the r-dimensional mesh of d-ary trees. RAIRO Theor. Inform. Appl.34 (2000) 515–519. Zbl0976.05059MR1844716
  15. [15] M. Yanakakis, A polynomial algorithm for the min-cut arrangement of trees. J. ACM32 (1985) 950–989. Zbl0633.68063

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.