Bandwidth on AT-free graphs
DOI10.1016/J.TCS.2011.09.011zbMATH Open1228.68036OpenAlexW1965845491MaRDI QIDQ650939FDOQ650939
Petr A. Golovach, Pinar Heggernes, Daniel Lokshtanov, Daniel Meister, Dieter Kratsch, Saket Saurabh
Publication date: 7 December 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.011
Recommendations
- Bandwidth on AT-free graphs
- scientific article; zbMATH DE number 3859182
- On bandwidth-2 graphs
- Bounding the bandwidths for graphs
- Publication:4940077
- Bandwidth of chain graphs
- On the size of graphs of a given bandwidth
- The bandwidth theorem in sparse graphs
- The bandwidth problem and operations on graphs
- scientific article; zbMATH DE number 3979113
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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?)
- Graph Classes: A Survey
- Optimal greedy algorithms for indifference graphs
- Parametrized complexity theory.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asteroidal Triple-Free Graphs
- The NP-completeness of the bandwidth minimization problem
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- 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
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- An optimal greedy heuristic to color interval graphs
- Triangulating graphs without asteroidal triples
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- Bandwidth of bipartite permutation graphs in polynomial time
- Title not available (Why is that?)
- Linear discrepancy and bandwidth
- Exact and Approximate Bandwidth
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Title not available (Why is that?)
Cited In (7)
- Title not available (Why is that?)
- Approximating the bandwidth for asteroidal triple-free graphs
- Interval degree and bandwidth of a graph
- Approximating the path-distance-width for AT-free graphs and graphs in related classes
- Bandwidth on AT-free graphs
- Line-distortion, bandwidth and path-length of a graph
- Two characterisations of the minimal triangulations of permutation graphs
Uses Software
This page was built for publication: Bandwidth on AT-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650939)
