Approximating the bandwidth for asteroidal triple-free graphs

DOI10.1007/3-540-60313-1_161zbMath1512.68235OpenAlexW1618256705MaRDI QIDQ6102320

Ton Kloks, Haiko Müller, Dieter Kratsch

Publication date: 8 May 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60313-1_161

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (17)

On claw-free asteroidal triple-free graphs ⋮ Restrictions of minimum spanner problems ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ On treewidth and minimum fill-in of asteroidal triple-free graphs ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Chordal embeddings of planar graphs ⋮ A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Asteroidal triples of moplexes ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Hardness and approximation of minimum distortion embeddings ⋮ Efficient algorithms for Roman domination on some classes of graphs ⋮ Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998 ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Listing all potential maximal cliques of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• On finding the minimum bandwidth of interval graphs
• Bandwidth of theta graphs with short paths
• The NP-completeness of the bandwidth minimization problem
• Treewidth. Computations and approximations
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Computing the Bandwidth of Interval Graphs
• On Comparability and Permutation Graphs
• Complexity of Finding Embeddings in a k-Tree
• On the Probable Performance of Heuristics for Bandwidth Minimization
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
• Algorithmic Aspects of Vertex Elimination on Graphs
• Complexity Results for Bandwidth Minimization
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Approximating the bandwidth for asteroidal triple-free graphs

This page was built for publication: Approximating the bandwidth for asteroidal triple-free graphs