Construction of a simple elimination scheme for a chordal comparability graph in linear time
type: Item
instance of: scholarly article
title: Construction of a simple elimination scheme for a chordal comparability graph in linear time
zbMATH Open document ID: 0924.05061
DOI: 10.1016/S0166-218X(98)00137-1
author: Richard B. Borie
author: Jeremy P. Spinrad
published in: Discrete Applied Mathematics
publication date: 1999-11-07T00:00:00Z
review text: Chordal graphs and comparability graphs are two classic graph classes playing a crucial role in algorithmic graph theory of perfect graphs. It is easy to see that chordal comparability graphs are strongly chordal---an important subclass of chordal graphs---and thus have a simple elimination ordering. This paper shows how to find such an ordering of a given chordal comparability graph by using cardinality lexicographic breadth-first search. This implies a linear time algorithm for the maximum matching problem on those graphs.
reviewed by: Andreas Brandstädt
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1271080
zbMATH Keywords: perfect graphs
zbMATH Keywords: chordal comparability graphs
zbMATH Keywords: simple elimination ordering
zbMATH Keywords: linear time algorithm
zbMATH Keywords: maximum matching problem
MaRDI profile type: Publication
cites work: Q4373681
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Transitiv orientierbare Graphen
cites work: Q3328583
cites work: Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
cites work: The dimension of cycle-free orders
cites work: A characterization of totally balanced hypergraphs
cites work: Cycle-free partial orders and chordal comparability graphs
cites work: Q5501778
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
Wikidata QID: Q127065923
Recommended article: An implicit representation of chordal comparability graphs in linear time
Recommended article: An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time
Recommended article: New linear time algorithms for generating perfect elimination orderings of chordal graphs
Recommended article: On some simplicial elimination schemes for chordal graphs
Recommended article: Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
Recommended article: Q4737226
Recommended article: An optimal time algorithm for minimum linear arrangement of chord graphs
Recommended article: A linear-time algorithm for isomorphism of a subclass of chordal graphs
Recommended article: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
Recommended article: Q3481747
description: scientific article; zbMATH DE number 1271080