Construction of a simple elimination scheme for a chordal comparability graph in linear time

DOI10.1016/S0166-218X(98)00137-1zbMath0924.05061WikidataQ127065923 ScholiaQ127065923MaRDI QIDQ1283807

Jeremy P. Spinrad, Richard B. Borie

Publication date: 7 November 1999

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

zbMATH Keywords

perfect graphslinear time algorithmsimple elimination orderingmaximum matching problemchordal comparability graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

From a simple elimination ordering to a strong elimination ordering in linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• A characterization of totally balanced hypergraphs
• Cycle-free partial orders and chordal comparability graphs
• The dimension of cycle-free orders
• Algorithmic Aspects of Vertex Elimination on Graphs
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Transitiv orientierbare Graphen