Induced matchings
type: Item
instance of: scholarly article
title: Induced matchings
zbMATH Open document ID: 0687.05033
DOI: 10.1016/0166-218X(92)90275-F
author: Kathie Cameron
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4125436
zbMATH Keywords: chordal graphs
zbMATH Keywords: induced matching
zbMATH Keywords: NP-complete
zbMATH Keywords: bipartite graph
zbMATH Keywords: parallel algorithm
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
Wikidata QID: Q61920235
cites work: Q3286847
cites work: Q3941433
cites work: A characterisation of rigid circuit graphs
cites work: On rigid circuit graphs
cites work: Characterizations of strongly chordal graphs
cites work: Q4093489
cites work: Incidence matrices and interval graphs
cites work: Q4198056
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Q3271426
cites work: Totally-Balanced and Greedy Matrices
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Representations of chordal graphs as subtrees of a tree
description: scientific article; zbMATH DE number 4125436