Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950586 | Information and Computation | 2017 | 16 Pages |
Abstract
This paper studies exact algorithms for the Maximum Induced Matching problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in Oâ(1.4231n) time and polynomial space or Oâ(1.3752n) time and exponential space.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mingyu Xiao, Huan Tan,