|
This article is cited in 3 scientific papers (total in 3 papers)
A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
V. V. Lepin Institute of Mathematics of the National Academy of Sciences of Belarus
Abstract:
An induced matching $M$ of a graph $G$ is a set of pairwise non-adjacent edges such that their end-vertices induce a 1-regular subgraph. An induced matching $M$ is maximal if no other induced matching contains $M$. The Minimum Induced Matching problem asks for a minimum maximal induced matching in a given graph. The problem is known to be NP-complete. Here we show that, if $G$ is a tree then this problem can be solved in linear time.
Received: 29.05.2007
Citation:
V. V. Lepin, “A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree”, Tr. Inst. Mat., 15:1 (2007), 78–90
Linking options:
https://www.mathnet.ru/eng/timb86 https://www.mathnet.ru/eng/timb/v15/i1/p78
|
Statistics & downloads: |
Abstract page: | 666 | Full-text PDF : | 283 | References: | 40 |
|