Hardness results for approximating the bandwidth
DOI10.1016/J.JCSS.2010.06.006zbMATH Open1215.68104OpenAlexW2090119011WikidataQ56767459 ScholiaQ56767459MaRDI QIDQ619902FDOQ619902
Walter Unger, Chandan K. Dubey, Uriel Feige
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.006
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Measured descent: A new embedding method for finite metrics
- Bandwidth of theta graphs with short paths
- The NP-completeness of the bandwidth minimization problem
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Computing the Bandwidth of Interval Graphs
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
- The bandwidth problem for graphs and matrices—a survey
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- On finding the minimum bandwidth of interval graphs
- Approximating the bandwidth via volume respecting embeddings
- Approximating Bandwidth by Mixing Layouts of Interval Graphs
- Graphs with small bandwidth and cutwidth
- Improved bandwidth approximation for trees and chordal graphs
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
Cited In (14)
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Retracting Graphs to Cycles
- Approximating bandwidth by mixing layouts of interval graphs
- Critical elements in combinatorially closed families of graph classes
- Bandwidth of convex bipartite graphs and related graphs
- Grid drawings of graphs with constant edge-vertex resolution
- Bandwidth and density for block graphs
- Ordering transactions with bounded unfairness: definitions, complexity and constructions
- Title not available (Why is that?)
- Exact and approximate bandwidth
- Bandwidth of graphs resulting from the edge clique covering problem
- Line-distortion, bandwidth and path-length of a graph
- Parameterized algorithms for minimum sum vertex cover
- Bandwidth contrained NP-complete problems
This page was built for publication: Hardness results for approximating the bandwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619902)
