Geodesic
A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
Trudy Instituta matematiki, Tome 15 (2007) no. 1, pp. 78-90

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TIMB_2007_15_1_a8,
     author = {V. V. Lepin},
     title = {A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree},
     journal = {Trudy Instituta matematiki},
     pages = {78--90},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a8/}
}
TY  - JOUR
AU  - V. V. Lepin
TI  - A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
JO  - Trudy Instituta matematiki
PY  - 2007
SP  - 78
EP  - 90
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a8/
LA  - ru
ID  - TIMB_2007_15_1_a8
ER  - 
%0 Journal Article
%A V. V. Lepin
%T A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree
%J Trudy Instituta matematiki
%D 2007
%P 78-90
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a8/
%G ru
%F TIMB_2007_15_1_a8
V. V. Lepin. A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree. Trudy Instituta matematiki, Tome 15 (2007) no. 1, pp. 78-90. http://geodesic.mathdoc.fr/item/TIMB_2007_15_1_a8/