Triangulating multitolerance graphs

DOI10.1016/S0166-218X(98)00026-2zbMath0908.05067MaRDI QIDQ1392575

Andreas Parra

Publication date: 28 July 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

treewidthtrapezoid graphspathwidthtolerance graphfill-in problemmultitolerance graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Memory requirements for table computations in partial k-tree algorithms, The recognition of triangle graphs, How to use the minimal separators of a graph for its chordal triangulation, An intersection model for multitolerance graphs: efficient algorithms and hierarchy, Tree-decompositions of small pathwidth, A characterization of interval orders with semiorder dimension two, Tree-decompositions of small pathwidth, New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial

Cites Work

• On a problem concerning tolerance graphs
• Tolerance graphs
• Graph minors. I. Excluding a forest
• Decomposition by clique separators
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Bipartite permutation graphs
• Trapezoid graphs and their coloring
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Bipartite tolerance orders
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Proper and unit tolerance graphs
• Triangulating graphs without asteroidal triples
• Triangulated graphs and the elimination process
• Easy problems for tree-decomposable graphs
• A Linear Recognition Algorithm for Cographs
• Graph minors. II. Algorithmic aspects of tree-width
• Computing the Minimum Fill-In is NP-Complete
• The Pathwidth and Treewidth of Cographs
• TREEWIDTH OF CIRCLE GRAPHS
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item