Hardness results for approximating the bandwidth

DOI10.1016/J.JCSS.2010.06.006MaRDI QIDQ619902zbMATH OpenOpenAlexWikidataFDO

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

(22)

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

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)