Finding a maximum induced matching in weakly chordal graphs (Q1810638)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Finding a maximum induced matching in weakly chordal graphs |
scientific article |
Statements
Finding a maximum induced matching in weakly chordal graphs (English)
0 references
9 June 2003
0 references
It is known that finding an induced matching of maximum cardinality in a graph is NP-hard. It is shown in this paper that a maximum induced matching in a weakly chordal graph can be found in polynomial time. This generalizes previously known results for the induced matching problem. This also demonstrates that the maximum induced matching problem in chordal bipartite graphs can be solved in polynomial time while the problem is known to be NP-hard for bipartite graphs in general.
0 references
induced matching
0 references
strong matching
0 references
strong edge-colouring
0 references
strong chromatic index
0 references
weakly chordal graphs
0 references
interval-filament graphs
0 references
intersection graphs
0 references
polynomial-time algorithm
0 references
