An exponential time 2-approximation algorithm for bandwidth

DOI10.1016/J.TCS.2013.03.024MaRDI QIDQ392018zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Shiva Prasad Kasiviswanathan, Martin Fürer

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

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

Recommendations

• An exponential time 2-approximation algorithm for bandwidth
• Exact and approximate bandwidth
• Exact and Approximate Bandwidth
• Even faster exact bandwidth
• Faster Exact Bandwidth

Cites work

• A mildly exponential approximation algorithm for the permanent
• 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
• An exponential time 2-approximation algorithm for bandwidth
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating the bandwidth of caterpillars
• Approximating the bandwidth via volume respecting embeddings
• Approximating the max-edge-coloring problem
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Approximation of min coloring by moderately exponential algorithms
• Bandwidth and distortion revisited
• Bandwidth of bipartite permutation graphs in polynomial time
• Bandwidth of chain graphs
• Bandwidth of convex bipartite graphs and related graphs
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Complexity Results for Bandwidth Minimization
• Computing the Bandwidth of Interval Graphs
• Confronting hardness using a hybrid approach
• Counting Subgraphs via Homomorphisms
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Even faster exact bandwidth
• Exact and approximate bandwidth
• Exponential-time approximation of weighted set cover
• Fixed-parameter approximation: conceptual framework and approximability results
• scientific article; zbMATH DE number 1617243 (Why is no real title available?)
• scientific article; zbMATH DE number 1186230 (Why is no real title available?)
• scientific article; zbMATH DE number 1833416 (Why is no real title available?)
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Linear FPT reductions and computational lower bounds
• MAX SAT approximation beyond the limits of polynomial-time approximation
• On finding the minimum bandwidth of interval graphs
• On Parameterized Approximability
• On the complexity of k-SAT
• Parameterized Approximation Problems
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Set partitioning via inclusion-exclusion
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The NP-completeness of the bandwidth minimization problem
• Volume distortion for subsets of Euclidean spaces
• Worst-case study of local search for MAX-\(k\)-SAT.

Cited in

(6)

• Sparsification and subexponential approximation
• Exact and Approximate Bandwidth
• An exponential time 2-approximation algorithm for bandwidth
• Bandwidth parameterized by cluster vertex deletion number
• Bandwidth parameterized by cluster vertex deletion number
• Exact and approximate digraph bandwidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392018)