AbstractA matching in a graph G is a collection of non-intersecting edges. The matching is induced if no two edges in the matching are joined by an edge in G. This paper studies the complexity of finding a largest induced matching when the input graph is a tree. We describe the first linear time algorithm for this problem.
Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: graphs, matching, induced, trees, algorithm
Selected references
- Fanica Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2):180-187, June 1972.
- Larry J. Stockmeyer and Vijay V. Vazirani. NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters, 15(1):14-19, 19 August 1982.