2014/04/24 by Ruzayn Quaddoura, Quaddoura, Ruzayn
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1404.6288
openalex publication_date 2014/04/24 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
A matching in a graph is a set of edges no two of which share a common vertex. A matching M is an induced matching if no edge connects two edges of M. The problem of finding a maximum induced matching is known to be NP-hard in general and specifically for bipartite graphs. Lozin has been proposed an O(n3) time algorithm for this problem on the class of bipartite Star123,Sun4-free graphs. In this paper we improve and generalize this result in presenting a simple O(n) time algorithm for maximum induced matching problem in bipartite Star123-free graphs.