Graph bandwidth of weighted caterpillars

DOI10.1016/j.tcs.2006.07.015zbMath1110.68110OpenAlexW2035656984MaRDI QIDQ860873

Jinhui Xu, Mingen Lin, Zhiyong Lin

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.015

zbMATH Keywords

algorithmcaterpillarlinear layout

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion ⋮ Multilevel Bandwidth and Radio Labelings of Graphs

Cites Work

• Bandwidth of chain graphs
• The NP-completeness of the bandwidth minimization problem
• Approximating the bandwidth via volume respecting embeddings
• Approximating Layout Problems on Random Geometric Graphs
• Improved Bandwidth Approximation for Trees and Chordal Graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Complexity Results for Bandwidth Minimization
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs