Bandwidth on AT-free graphs

DOI10.1016/J.TCS.2011.09.011MaRDI QIDQ650939zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, 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

zbMATH Keywords

bandwidthalgorithmfixed-parameter tractableAT-free graph

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1696538 (Why is no real title available?)
• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 1186230 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An optimal greedy heuristic to color interval graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Computing the Bandwidth of Interval Graphs
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Exact and Approximate Bandwidth
• Graph Classes: A Survey
• Linear discrepancy and bandwidth
• Optimal greedy algorithms for indifference graphs
• Parametrized complexity theory.
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• 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
• Triangulating graphs without asteroidal triples

Cited in

(8)

• scientific article; zbMATH DE number 1151836 (Why is no real title available?)
• 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
• Parameterized complexity of bandwidth on trees
• Line-distortion, bandwidth and path-length of a graph
• Two characterisations of the minimal triangulations of permutation graphs

Describes a project that uses

Uses Software

• symrcm

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)