Construction of a simple elimination scheme for a chordal comparability graph in linear time (Q1283807)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1271080
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Construction of a simple elimination scheme for a chordal comparability graph in linear time |
scientific article; zbMATH DE number 1271080 |
Statements
Construction of a simple elimination scheme for a chordal comparability graph in linear time (English)
0 references
7 November 1999
0 references
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.
0 references
perfect graphs
0 references
chordal comparability graphs
0 references
simple elimination ordering
0 references
linear time algorithm
0 references
maximum matching problem
0 references
0 references
0.92558336
0 references
0.9230151
0 references
0.9052669
0 references
0.8974076
0 references
0.8904915
0 references
0.87061244
0 references
0 references
0.86446583
0 references
