Approximating the Bandwidth for Asteroidal Triple-Free Graphs
From MaRDI portal
Publication:4719340
DOI10.1006/JAGM.1998.0997zbMath0951.68113OpenAlexW2062004151MaRDI QIDQ4719340
Haiko Müller, Dieter Kratsch, Ton Kloks
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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (26)
Boxicity and treewidth ⋮ Two characterisations of the minimal triangulations of permutation graphs ⋮ Detecting induced minors in AT-free graphs ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Hardness results for approximating the bandwidth ⋮ Cubicity and bandwidth ⋮ Interval degree and bandwidth of a graph ⋮ Approximating the treewidth of AT-free graphs. ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ Algorithms for graphs with small octopus ⋮ Bandwidth on AT-free graphs ⋮ On treewidth approximations. ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ Bandwidth of Bipartite Permutation Graphs in Polynomial Time ⋮ On the domination search number ⋮ Unnamed Item ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ On the Cubicity of AT-Free Graphs and Circular-Arc Graphs ⋮ Classes of graphs with \(e\)-positive chromatic symmetric function ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES ⋮ Treewidth of planar graphs: connections with duality
This page was built for publication: Approximating the Bandwidth for Asteroidal Triple-Free Graphs
