Induced matchings (Q1262877)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Induced matchings |
scientific article; zbMATH DE number 4125436
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Induced matchings |
scientific article; zbMATH DE number 4125436 |
Statements
Induced matchings (English)
0 references
1989
0 references
An induced matching of a graph G is a vertex induced subgraph of G that is a matching. The author shows that the following decision problem is NP-complete: For a given bipartite graph G and positive integer k, is there an induced matching of size at least k? So the problem of finding a largest induced matching for bipartite graphs is Np-hard. It is, however, shown that there is an efficient parallel algorithm for finding largest induced matchings in chordal graphs.
0 references
chordal graphs
0 references
induced matching
0 references
NP-complete
0 references
bipartite graph
0 references
parallel algorithm
0 references
