Approximating the bandwidth of caterpillars
From MaRDI portal
Publication:2391175
DOI10.1007/s00453-007-9002-0zbMath1194.68170MaRDI QIDQ2391175
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
68R10: Graph theory (including graph drawing) in computer science
Related Items
An exponential time 2-approximation algorithm for bandwidth, Exact and approximate bandwidth, Reconfiguration in bounded bandwidth and tree-depth, Capacitated domination faster than \(O(2^n)\), On the bandwidth of the Kneser graph
Cites Work
- 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
- Unnamed Item
- Unnamed Item