An exponential time 2-approximation algorithm for bandwidth
DOI10.1016/J.TCS.2013.03.024zbMATH Open1407.68545OpenAlexW1781900113MaRDI QIDQ392018FDOQ392018
Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Parameterized Approximation Problems
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- On the complexity of \(k\)-SAT
- Confronting hardness using a hybrid approach
- A mildly exponential approximation algorithm for the permanent
- Set Partitioning via Inclusion-Exclusion
- The NP-completeness of the bandwidth minimization problem
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Bandwidth of chain graphs
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Computing the Bandwidth of Interval Graphs
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- Complexity Results for Bandwidth Minimization
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Exact and approximate bandwidth
- Approximating the max-edge-coloring problem
- Linear FPT reductions and computational lower bounds
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- 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
- Worst-case study of local search for MAX-\(k\)-SAT.
- Approximating the bandwidth via volume respecting embeddings
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- Fixed-parameter approximation: conceptual framework and approximability results
- Approximating the bandwidth of caterpillars
- Title not available (Why is that?)
- Bandwidth of Convex Bipartite Graphs and Related Graphs
- Even Faster Exact Bandwidth
- On Parameterized Approximability
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Title not available (Why is that?)
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Bandwidth and distortion revisited
- Title not available (Why is that?)
- Counting Subgraphs via Homomorphisms
- MAX SAT approximation beyond the limits of polynomial-time approximation
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
Cited In (2)
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)
