Approximating the Bandwidth for Asteroidal Triple-Free Graphs

DOI10.1006/JAGM.1998.0997MaRDI QIDQ4719340zbMATH OpenOpenAlexFDO

Authors Ton Kloks, Dieter Kratsch, Haiko Müller

Publication date 18 December 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1998.0997

zbMATH Keywords

AT-free graphbandwidth minimization problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximating the bandwidth for asteroidal triple-free graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Asteroidal-triple-free interval \(k\)-graphs
• Asteroidal Triple-Free Graphs
• Asteroidal triple-free graphs
• Bounding the bandwidths for graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• scientific article; zbMATH DE number 3900798
• On the structure of graphs with bounded asteroidal number

Cited in

(28)

• Bandwidth of bipartite permutation graphs in polynomial time
• Interval degree and bandwidth of a graph
• Approximating the treewidth of AT-free graphs.
• Algorithms for graphs with small octopus
• On treewidth approximations.
• Tractabilities and intractabilities on geometric intersection graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• On the domination search number
• Cubicity and bandwidth
• Classes of graphs with \(e\)-positive chromatic symmetric function
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• Boxicity and treewidth
• Approximability of the path-distance-width for AT-free graphs
• Treewidth of planar graphs: connections with duality
• Bandwidth on AT-free graphs
• On the cubicity of AT-free graphs and circular-arc graphs
• Two characterisations of the minimal triangulations of permutation graphs
• Detecting induced minors in AT-free graphs
• An exponential time 2-approximation algorithm for bandwidth
• Bandwidth of convex bipartite graphs and related graphs
• On the minimum chordal completion polytope
• Line-distortion, bandwidth and path-length of a graph
• A CHARACTERIZATION OF k-TH POWERS P_n,k OF PATHS IN TERMS OF k-TREES
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Approximating the bandwidth for asteroidal triple-free graphs
• Hardness results for approximating the bandwidth
• Bandwidth on AT-free graphs
• Boxicity and cubicity of asteroidal triple free graphs

This page was built for publication: Approximating the Bandwidth for Asteroidal Triple-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4719340)