Hardness results for approximating the bandwidth

DOI10.1016/j.jcss.2010.06.006zbMath1215.68104OpenAlexW2090119011WikidataQ56767459 ScholiaQ56767459MaRDI QIDQ619902

Uriel Feige, Walter Unger, Chandan K. Dubey

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

zbMATH Keywords

bandwidthcircular arc graphcaterpillargap amplification

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Grid drawings of graphs with constant edge-vertex resolution ⋮ Bandwidth of graphs resulting from the edge clique covering problem ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Retracting Graphs to Cycles ⋮ Critical elements in combinatorially closed families of graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs with small bandwidth and cutwidth
• On finding the minimum bandwidth of interval graphs
• Bandwidth of theta graphs with short paths
• The NP-completeness of the bandwidth minimization problem
• Approximating the bandwidth via volume respecting embeddings
• Measured descent: A new embedding method for finite metrics
• Improved Bandwidth Approximation for Trees and Chordal Graphs
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

This page was built for publication: Hardness results for approximating the bandwidth