An exponential time 2-approximation algorithm for bandwidth

DOI10.1016/j.tcs.2013.03.024zbMath1407.68545MaRDI 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 algorithm; bucket decomposition; exponential time algorithm; graph bandwidth

Mathematics Subject Classification ID

68W40: Analysis of algorithms

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

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

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