A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree

V. V. Lepin

Trudy Instituta matematiki, Tome 15 (2007) no. 1, pp. 78-90.

Résumé

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.

Bibliographie

[1] Stockmeyer L.J., Vazirani V.V., “NP-completeness of some generalizations of the maximum matching problem”, Inform. Process. Lett., 15 (1982), 14–19 | DOI | MR | Zbl

[2] Golumbic M.C., Laskar R., “Irredundancy in circular arc graphs”, Discrete Appl. Math., 44 (1993), 79–89 | DOI | MR | Zbl

[3] Cameron K., “Induced matchings”, Discrete Appl. Math., 24 (1989), 97–102 | DOI | MR | Zbl

[4] Golumbic M.C., Lewenstein M., “New results on induced matchings”, Discrete Appl. Math., 101 (2000), 157–165 | DOI | MR | Zbl

[5] Duckworth W., Wormald N.C., Zito M., “Maximum induced matchings of random cubic graphs”, J. Comput. Appl. Math., 142 (2002), 39–50 | DOI | MR | Zbl

[6] Erdos P., “Problems and results in combinatorial analysis and graph theory”, Discrete Math., 78 (1988), 81–92 | DOI | MR

[7] Faudree R.J., Gyarfas A., Schelp R.H., Tuza Z., “Induced matchings in bipartite graphs”, Discrete Math., 78:1-2 (1989), 83–87 | DOI | MR | Zbl

[8] Liu J., Zhou H., “Maximum induced matchings in graphs”, Discrete Math., 170 (1997), 271–281 | DOI | MR

[9] Steger A., Yu M., “On induced matchings”, Discrete Math., 120 (1993), 291–295 | DOI | MR | Zbl

[10] Duckworth W., Manlove D., Zito M., “On the approximability of the maximum induced matching problem”, J. Discrete Algorithms, 3 (2005), 79–91 | DOI | MR | Zbl

[11] Orlovich Yu.L., Zverovich I.E., Well-matched graphs, RUTCOR Research Report 12-2004, Rutgers University, Rutgers, 2004

[12] Orlovich Yu.L., Zverovich I.E., Maximal induced matchings of minimum /~maximum size, DIMACS Technical Report 2004-26, Rutgers University, Rutgers, 2004

[13] Orlovich Yu., Finke G., Gordon V., Zverovich I., Approximability for the minimum and maximum induced matching problems, Les cahiers Leibniz, No 130, University Joseph Fourier, Laboratory LEIBNIZ-IMAG, 2005; in English; available at http:www-leibniz.imag.fr

[14] Richey M.B., Parker R.G., “Minimum-maximal matching in series-parallel graphs”, European J. Operational Research, 33 (1987), 98–105 | DOI | MR

[15] Zito M., “Small Maximal Matchings in Random Graphs”, LATIN 2000: Theoretical Informatics; 4th Latin American Symposium, Lecture Notes in Computer Science, 1776, eds. G.H. Gonnet, D. Panario, and A. Viola, 2000, 18–27 | Zbl

[16] Chang J.-M., “Induced matchings in asteroidal triple-free graphs”, Discrete Appl. Math., 132 (2004), 67–78 | DOI | MR

[17] Kobler D., Rotics U., “Finding maximum induced matchings in subclasses of claw-free and P 5-free graphs, and in graphs with matching and induced matching of equal maximum size”, Algorithmica, 37 (2003), 327–346 | DOI | MR | Zbl

[18] Liu J., Zhou H., “Maximum induced matchings in graphs”, Discrete Math., 170 (1997), 271–281 | DOI | MR

[19] Duckworth W., Manlove D., Zito M., “On the approximability of the maximum induced matching problem”, J. Discrete Algorithms, 3:1, 79–91 | DOI | MR | Zbl

[20] Fricke G., Laskar R., “Strong matchings on trees”, Congr. Numer., 89 (1992), 239–243 | MR | Zbl

[21] Zito M., “Linear Time Maximum Induced Matching Algorithm for Trees”, Nordic J. of Computing, 7 (2000), 58–63 | MR | Zbl