Triangulating graphs without asteroidal triples

DOI10.1016/0166-218X(95)00095-9MaRDI QIDQ1917255zbMATH OpenOpenAlexFDO

Authors Rolf H. Möhring

Publication date 7 July 1996

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(95)00095-9

zbMATH Keywords

treewidthasteroidal triple

Mathematics Subject Classification ID

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

Recommendations

• Asteroidal Triple-Free Graphs
• Asteroidal Triple of Edges in Bichordal Graphs: A Complete list
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• scientific article; zbMATH DE number 1262790

Cites work

• scientific article; zbMATH DE number 4173000 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147519 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 219228 (Why is no real title available?)
• scientific article; zbMATH DE number 833244 (Why is no real title available?)
• Asteroidal Triple-Free Graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Decomposition by clique separators
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• On the pathwidth of chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• The Pathwidth and Treewidth of Cographs
• Tolerance graphs
• Treewidth and pathwidth of permutation graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Treewidth. Computations and approximations
• Triangulated graphs and the elimination process

Cited in

(29)

• Asteroidal Triple of Edges in Bichordal Graphs: A Complete list
• A Characterisation of the Minimal Triangulations of Permutation Graphs
• Asteroidal triples of moplexes
• Bandwidth on AT-free graphs
• Separator orders in interval, cocomparability, and AT-free graphs
• Treewidth and minimum fill-in on permutation graphs in linear time
• Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
• On a property of minimal triangulations
• Treewidth and logical definability of graph products
• Representing a concept lattice by a graph
• Tree-decompositions of small pathwidth
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Boxicity and cubicity of asteroidal triple free graphs
• A partial k-arboretum of graphs with bounded treewidth
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Interval degree and bandwidth of a graph
• Minimal triangulations of graphs: a survey
• Tree-decompositions of small pathwidth
• Recognizing graphs without asteroidal triples
• On the interval completion of chordal graphs
• The complexity of subgraph isomorphism for classes of partial k-trees
• Triangulating multitolerance graphs
• Tree-width and path-width of comparability graphs of interval orders
• Independent sets in asteroidal triple-free graphs
• Asteroidal-triple-free interval \(k\)-graphs
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Triangulating graphs with few \(P_4\)'s
• Two characterisations of the minimal triangulations of permutation graphs

This page was built for publication: Triangulating graphs without asteroidal triples

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