Abstract
A connected matching M in a graph G is a matching such that every pair of edges of M is joined by an edge of G. Plummer, Stiebitz and Toft introduced connected matchings in connection with their study of the famous Hadwiger Conjecture. In this paper, I prove that the connected matching problem is NP-complete for 0-1-weighted bipartite graphs, but polytime-solvable for chordal graphs and for graphs with no circuits of size 4.
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
Kathie Cameron, Induced matchings, Discrete Applied Mathematics 24 (1989), 97–102.
Kathie Cameron, Induced matchings in Intersection Graphs, 3-page abstract in: Electronic Notes in Discrete Mathematics 5 (2000); paper submitted for publication.
Kathie Cameron, R. Sritharan, and Yingwen Tang, accepted for publication in Discrete Mathematics.
Jou-Ming Chang, Induced matchings in asteroidal triple-free graphs, manuscript, April 2001.
G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.
Jack Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449–467.
Jack Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125–130.
F. Gavril, Maximum weight independent sets and cliques in intersection graphs of filaments, Information Processing Letters 73 (2000), 181–188.
Martin Charles Golumbic and Renu C. Laskar, Irredundancy in circular-arc graphs, Discrete Applied Mathematics 44 (1993), 79–89.
Martin Charles Golumbic and Moshe Lewenstein, New results on induced matchings, Discrete Applied Mathematics 101 (2000), 157–165.
S. Janson and J. Kratochvil, Threshold functions for classes of intersection graphs, Discrete Mathematics 108 (1992), 307–326.
C. W. Ko and F.B. Shepherd, Adding an identity to a totally unimodular matrix, London School of Economics Operations Research Working Paper, LSEOR 94.14, July 1994.
Alexandr Kostochka and Jan Kratochvíl, Covering and coloring polygon-circle graphs, Discrete Mathematics 163 (1997), 299–305.
Michael D. Plummer, Michael Stiebitz and Bjarne Toft, On a special case of Hadwiger’s conjecture, manuscript June 2001.
Larry J. Stockmeyer and Vijay V. Vazirani, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters 15 (1982), 14–19.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Cameron, K. (2003). Connected Matchings. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds) Combinatorial Optimization — Eureka, You Shrink!. Lecture Notes in Computer Science, vol 2570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36478-1_5
Download citation
DOI: https://doi.org/10.1007/3-540-36478-1_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00580-3
Online ISBN: 978-3-540-36478-8
eBook Packages: Springer Book Archive