An exponential time 2-approximation algorithm for bandwidth

DOI10.1016/j.tcs.2013.03.024zbMath1407.68545OpenAlexW1781900113MaRDI QIDQ392018

Serge Gaspers, Shiva Prasad Kasiviswanathan, Martin Fuerer

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.024

zbMATH Keywords

approximation algorithmbucket decompositionexponential time algorithmgraph bandwidth

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

Sparsification and subexponential approximation ⋮ On subexponential and FPT-time inapproximability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth of chain graphs
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Bandwidth and distortion revisited
• Exact and approximate bandwidth
• Approximating the max-edge-coloring problem
• Approximation of min coloring by moderately exponential algorithms
• Exponential-time approximation of weighted set cover
• Volume distortion for subsets of Euclidean spaces
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Bandwidth of bipartite permutation graphs in polynomial time
• On finding the minimum bandwidth of interval graphs
• The NP-completeness of the bandwidth minimization problem
• Worst-case study of local search for MAX-\(k\)-SAT.
• Approximating the bandwidth via volume respecting embeddings
• A mildly exponential approximation algorithm for the permanent
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Fixed-parameter approximation: conceptual framework and approximability results
• Approximating the bandwidth of caterpillars
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Bandwidth of Convex Bipartite Graphs and Related Graphs
• Even Faster Exact Bandwidth
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Computing the Bandwidth of Interval Graphs
• On Parameterized Approximability
• Parameterized Approximation Problems
• Set Partitioning via Inclusion-Exclusion
• Linear FPT reductions and computational lower bounds
• Confronting hardness using a hybrid approach
• An Exponential Time 2-Approximation Algorithm for Bandwidth
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Complexity Results for Bandwidth Minimization
• A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Counting Subgraphs via Homomorphisms
• On the complexity of \(k\)-SAT
• MAX SAT approximation beyond the limits of polynomial-time approximation

This page was built for publication: An exponential time 2-approximation algorithm for bandwidth