Triangulating multitolerance graphs

DOI10.1016/S0166-218X(98)00026-2MaRDI QIDQ1392575zbMATH OpenFDO

Authors 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

treewidthpathwidthtrapezoid graphstolerance graphfill-in problemmultitolerance graph

Mathematics Subject Classification ID

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

Recommendations

• New geometric representations and domination problems on tolerance and multitolerance graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• New geometric representations and domination problems on tolerance and multitolerance graphs.
• Minimum Fill-in on Circle and Circular-Arc Graphs

Cites work

• scientific article; zbMATH DE number 432839 (Why is no real title available?)
• scientific article; zbMATH DE number 3853140 (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 512915 (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 4121438 (Why is no real title available?)
• scientific article; zbMATH DE number 6157240 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Bipartite permutation graphs
• Bipartite tolerance orders
• Computing the Minimum Fill-In is NP-Complete
• Decomposition by clique separators
• Easy problems for tree-decomposable graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On a problem concerning tolerance graphs
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• Proper and unit tolerance graphs
• TREEWIDTH OF CIRCLE GRAPHS
• The Pathwidth and Treewidth of Cographs
• Tolerance graphs
• Trapezoid graphs and their coloring
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Triangulated graphs and the elimination process
• Triangulating graphs without asteroidal triples

Cited in

(10)

• New geometric representations and domination problems on tolerance and multitolerance graphs
• scientific article; zbMATH DE number 29611 (Why is no real title available?)
• Memory requirements for table computations in partial k-tree algorithms
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• The recognition of triangle graphs
• How to use the minimal separators of a graph for its chordal triangulation
• Tree-decompositions of small pathwidth
• A characterization of interval orders with semiorder dimension two
• Tree-decompositions of small pathwidth
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy

This page was built for publication: Triangulating multitolerance graphs

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