Approximating the bandwidth of caterpillars

DOI10.1007/s00453-007-9002-0zbMath1194.68170OpenAlexW2180413174MaRDI QIDQ2391175

Kunal Talwar, Uriel Feige

Publication date: 24 July 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9002-0

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

An exponential time 2-approximation algorithm for bandwidth ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Exact and approximate bandwidth ⋮ On the bandwidth of the Kneser graph

Cites Work

• Unnamed Item
• Unnamed Item
• Graphs with small bandwidth and cutwidth
• Approximating the bandwidth via volume respecting embeddings
• Measured descent: A new embedding method for finite metrics
• 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
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Bandwidth Minimization: An approximation algorithm for caterpillars

This page was built for publication: Approximating the bandwidth of caterpillars