Approximating the bandwidth of caterpillars

DOI10.1007/S00453-007-9002-0MaRDI QIDQ2391175zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1617243 (Why is no real title available?)
• scientific article; zbMATH DE number 1833416 (Why is no real title available?)
• Approximating the bandwidth via volume respecting embeddings
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Graphs with small bandwidth and cutwidth
• Improved bandwidth approximation for trees and chordal graphs
• 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

Cited in

(13)

• An exponential time 2-approximation algorithm for bandwidth
• Hardness results for approximating the bandwidth
• Rollercoasters and caterpillars
• Algorithmic Applications in Management
• scientific article; zbMATH DE number 1472394 (Why is no real title available?)
• 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)