An exponential time 2-approximation algorithm for bandwidth
From MaRDI portal
Publication:392018
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
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
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