An Exponential Time 2-Approximation Algorithm for Bandwidth

DOI10.1007/978-3-642-11269-0_14zbMath1273.68408arXiv0906.1953OpenAlexW2570928651MaRDI QIDQ3656860

Shiva Prasad Kasiviswanathan, Serge Gaspers, Martin Fuerer

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0906.1953

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

An exponential time 2-approximation algorithm for bandwidth ⋮ Exponential approximation schemata for some network design problems ⋮ Super-polynomial approximation branching algorithms ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Algorithms for dominating clique problems ⋮ Exact and approximate bandwidth ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth ⋮ Moderately exponential time and fixed parameter approximation algorithms

Cites Work

• Exponential-time approximation of weighted set cover
• Volume distortion for subsets of Euclidean spaces
• The NP-completeness of the bandwidth minimization problem
• Approximating the bandwidth via volume respecting embeddings
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Even Faster Exact Bandwidth
• Linear FPT reductions and computational lower bounds
• Confronting hardness using a hybrid approach
• Exact and Approximate Bandwidth
• An Exponential Time 2-Approximation Algorithm for Bandwidth
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Complexity Results for Bandwidth Minimization
• Faster Exact Bandwidth
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Counting Subgraphs via Homomorphisms
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item

This page was built for publication: An Exponential Time 2-Approximation Algorithm for Bandwidth