Bandwidth on AT-free graphs

DOI10.1016/j.tcs.2011.09.011zbMath1228.68036OpenAlexW1965845491MaRDI QIDQ650939

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

zbMATH Keywords

algorithmbandwidthfixed-parameter tractableAT-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Two characterisations of the minimal triangulations of permutation graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Line-distortion, bandwidth and path-length of a graph

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal greedy heuristic to color interval graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• The NP-completeness of the bandwidth minimization problem
• Linear discrepancy and bandwidth
• Triangulating graphs without asteroidal triples
• Optimal greedy algorithms for indifference graphs
• Parametrized complexity theory.
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• Exact and Approximate Bandwidth
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Graph Classes: A Survey
• Asteroidal Triple-Free Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques

This page was built for publication: Bandwidth on AT-free graphs