Hardness results for approximating the bandwidth

DOI10.1016/J.JCSS.2010.06.006MaRDI QIDQ619902zbMATHOpenAlexWikidataFDO

Authors 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

zbMATH Keywords

bandwidthcaterpillarcircular arc graphgap amplification

Mathematics Subject Classification ID

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximating the bandwidth of caterpillars
• Bandwidth of bipartite permutation graphs in polynomial time
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Improved bandwidth approximation for trees and chordal graphs

Cites work

• scientific article; zbMATH DE number 1617243 (Why is no real title available?)
• scientific article; zbMATH DE number 1696538 (Why is no real title available?)
• scientific article; zbMATH DE number 5506210 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1833416 (Why is no real title available?)
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating the bandwidth via volume respecting embeddings
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Bandwidth of theta graphs with short paths
• Computing the Bandwidth of Interval Graphs
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Graphs with small bandwidth and cutwidth
• Improved bandwidth approximation for trees and chordal graphs
• Measured descent: A new embedding method for finite metrics
• On finding the minimum bandwidth of interval graphs
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• 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
• The bandwidth problem for graphs and matrices—a survey

Cited in

(20)

• On Some Variants of the Bandwidth Minimization Problem
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Bandwidth of convex bipartite graphs and related graphs
• scientific article; zbMATH DE number 1775392 (Why is no real title available?)
• Bandwidth and density for block graphs
• Parameterized algorithms for minimum sum vertex cover
• Approximating the bandwidth of caterpillars
• Grid drawings of graphs with constant edge-vertex resolution
• Exact and approximate bandwidth
• Critical elements in combinatorially closed families of graph classes
• scientific article; zbMATH DE number 1778090 (Why is no real title available?)
• Bandwidth of convex bipartite graphs and related graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Bandwidth of graphs resulting from the edge clique covering problem
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Ordering transactions with bounded unfairness: definitions, complexity and constructions
• Line-distortion, bandwidth and path-length of a graph
• Approximating bandwidth by mixing layouts of interval graphs
• Retracting Graphs to Cycles
• 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)