New results on induced matchings
type: Item
instance of: scholarly article
title: New results on induced matchings
zbMATH Open document ID: 0951.68104
DOI: 10.1016/S0166-218X(99)00194-8
author: Martin Charles Golumbic
author: Moshe Lewenstein
published in: Discrete Applied Mathematics
publication date: 2000-12-11T00:00:00Z
review text: The paper concerns graphs \(G=\langle V,E\rangle.\) The induced matching \(M\subseteq E\) contains a subset of edges of \(E\) that no two edges \(e_{i}\) and \(e_{j}\) in \(M \) share a common vertex \(v\in V\) and there is no \(e\in E\) connecting \(e_{i}\) and \(e_{j}.\) So, induced matching is matching that no two edges are connected in \(G\). The general problem of finding maximum induced matching is NP-complete and is also related to independent set and to clique. The text concerns polynomial time algorithms for wide classes of graphs. The authors recalling earlier results on maximum independent set conclude that polynomial time algorithms exist for circular arc and for chordal graphs. It is proved that maximum induced matching can be found in polynomial time for trapezoid graphs or for cocomparability graphs. For interval graphs or for trees maximum induced matching can be found in linear time and the algorithms are provided. The defined maximum induced matching is valid for graph theory since it can be used as a ``'measurement'' of graph irredundancy. Moreover, it can be used for modelling tasks concerning network communication, VLSI design, and other combinatorial tasks.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C17
zbMATH DE Number: 1428630
zbMATH Keywords: graph theory
zbMATH Keywords: perfect graph
zbMATH Keywords: matching
zbMATH Keywords: induced matching
zbMATH Keywords: strong matching
zbMATH Keywords: independent set
reviewed by: Adam Kapralski
MaRDI profile type: Publication
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Induced matchings
cites work: Q4250178
cites work: Trapezoid graphs and their coloring
cites work: Trapezoid graphs and generalizations, geometry and algorithms
cites work: Q3139292
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Comparability graphs and a new matroid
cites work: Q3328583
cites work: Stability in circular arc graphs
cites work: Irredundancy in circular arc graphs
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
cites work: Linear time algorithms on circular-arc graphs
cites work: Minimum Cuts for Circular-Arc Graphs
full work available at URL: s0166-218x(99)00194-8
OpenAlex ID: W1974366154
description: scientific article; zbMATH DE number 1428630