Graph bandwidth of weighted caterpillars

DOI10.1016/J.TCS.2006.07.015zbMATH Open1110.68110OpenAlexW2035656984MaRDI QIDQ860873FDOQ860873

Authors Mingen Lin, Zhiyong Lin, Jinhui Xu

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) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithmic Applications in Management
• scientific article; zbMATH DE number 3859182
• Bandwidth of chain graphs
• Bounding the bandwidths for graphs
• Edge-Bandwidth of Graphs
• scientific article; zbMATH DE number 3963886
• On bandwidth sums of graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximating the bandwidth of caterpillars
• On the size of graphs of a given bandwidth

Cites work

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

Cited in

(9)

• Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
• Multilevel Bandwidth and Radio Labelings of Graphs
• An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
• Bandwidth Minimization: An approximation algorithm for caterpillars
• A quartic kernel for pathwidth-one vertex deletion
• Algorithmic Applications in Management
• The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete

This page was built for publication: Graph bandwidth of weighted caterpillars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q860873)