Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Induced Matching in Some Subclasses of Bipartite Graphs
verfasst von : Arti Pandey, B. S. Panda, Piyush Dane, Manav Kashyap
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
For a graph \(G=(V,E)\), a set \(M\subseteq E\) is called a matching in G if no two edges in M share a common vertex. A matching M in G is called an induced matching in G if G[M], the subgraph of G induced by M, is same as G[S], the subgraph of G induced by \(S=\{v \in V |\) v is incident on an edge of M\(\}\). The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. Given a graph G and a positive integer k, the Induced Matching Decision problem is to decide whether G has an induced matching of cardinality at least k. The Induced Matching Decision problem is NP-complete on bipartite graphs, but polynomial time solvable for convex bipartite graphs. In this paper, we show that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs and perfect elimination bipartite graphs. On the positive side, we propose polynomial time algorithms to solve the Maximum Induced Matching problem in circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial reductions from the Maximum Induced Matching problem in these graph classes to the Maximum Induced Matching problem in convex bipartite graphs.