New results on induced matchings (Q1975379)

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.