Abstract
Yannakakis and Gavril showed in [10] that the problem of finding a maximal matching of minimum size (MMM for short), also called Minimum Edge Dominating Set, is NP-hard in bipartite graphs of maximum degree 3 or planar graphs of maximum degree 3. Horton and Kilakos extended this result to planar bipartite graphs and planar cubic graphs [6]. Here, we extend the result of Yannakakis and Gavril in [10] by showing that MMM is NP-hard in the class of k-regular bipartite graphs for all k ≥ 3 fixed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alkan, A.: Current Trends in Economics: Theory and Applications, pp. 30–39. Springer, Heidelberg (1999)
Balinski, M., Sönmez, T.: A Tale of Two Mechanisms: Student placement. Journal of Economic Theory 84, 73–94 (1999)
Fujito, T., Nagamochi, H.: A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics 118, 199–207 (2002)
Gale, D., Shapley, I.S.: College admissions and the stability of marriage. Amer. Math. Montly 69, 9–14 (1962)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1994)
Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Disc. Math. 6(3), 375–387 (1993)
Hwang, S.F., Chang, G.J.: The edge domination problem. Discuss. Math. Graph. Theory 15(1), 51–57 (1995)
Mitchell, S.L., Hedetniemi, S.T.: Edge domination in trees. In: Proc. of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), pp. 489–509 (1977)
Srinivasan, A., Madhukar, K., Nagavamsi, P., Pandu Rangan, C., Chang, M.-S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Inform. Process. Lett. 56(3), 165–171 (1995)
Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38, 364–372 (1980)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Demange, M., Ekim, T. (2008). Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs. In: Agrawal, M., Du, D., Duan, Z., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2008. Lecture Notes in Computer Science, vol 4978. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79228-4_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-79228-4_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79227-7
Online ISBN: 978-3-540-79228-4
eBook Packages: Computer ScienceComputer Science (R0)