Approximating the bandwidth of caterpillars
From MaRDI portal
Publication:2391175
DOI10.1007/S00453-007-9002-0zbMATH Open1194.68170OpenAlexW2180413174MaRDI QIDQ2391175FDOQ2391175
Authors: 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
Recommendations
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Hardness results for approximating the bandwidth
- Bandwidth Minimization: An approximation algorithm for caterpillars
- scientific article; zbMATH DE number 1445378
- Improved bandwidth approximation for trees and chordal graphs
Cites Work
- Measured descent: A new embedding method for finite metrics
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- The bandwidth problem for graphs and matrices—a survey
- Approximating the bandwidth via volume respecting embeddings
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graphs with small bandwidth and cutwidth
- Improved bandwidth approximation for trees and chordal graphs
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Bandwidth Minimization: An approximation algorithm for caterpillars
Cited In (13)
- An exponential time 2-approximation algorithm for bandwidth
- Hardness results for approximating the bandwidth
- Rollercoasters and caterpillars
- Algorithmic Applications in Management
- Title not available (Why is that?)
- Capacitated domination faster than \(O(2^n)\)
- Graph bandwidth of weighted caterpillars
- Reconfiguration in bounded bandwidth and tree-depth
- On the bandwidth of the Kneser graph
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
- Exact and approximate bandwidth
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
This page was built for publication: Approximating the bandwidth of caterpillars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391175)
