Skip to main content
SpringerLink
Log in

Connected Matchings

  • Chapter
  • First Online:
Combinatorial Optimization — Eureka, You Shrink!

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2570))

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

Log in via an institution
eBook
USD 16.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 16.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Kathie Cameron, Induced matchings, Discrete Applied Mathematics 24 (1989), 97–102.

    Article  MATH  MathSciNet  Google Scholar 

  2. Kathie Cameron, Induced matchings in Intersection Graphs, 3-page abstract in: Electronic Notes in Discrete Mathematics 5 (2000); paper submitted for publication.

    Google Scholar 

  3. Kathie Cameron, R. Sritharan, and Yingwen Tang, accepted for publication in Discrete Mathematics.

    Google Scholar 

  4. Jou-Ming Chang, Induced matchings in asteroidal triple-free graphs, manuscript, April 2001.

    Google Scholar 

  5. G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71–76.

    Article  MATH  MathSciNet  Google Scholar 

  6. Jack Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449–467.

    MATH  MathSciNet  Google Scholar 

  7. Jack Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125–130.

    MathSciNet  Google Scholar 

  8. F. Gavril, Maximum weight independent sets and cliques in intersection graphs of filaments, Information Processing Letters 73 (2000), 181–188.

    Article  MathSciNet  Google Scholar 

  9. Martin Charles Golumbic and Renu C. Laskar, Irredundancy in circular-arc graphs, Discrete Applied Mathematics 44 (1993), 79–89.

    Article  MATH  MathSciNet  Google Scholar 

  10. Martin Charles Golumbic and Moshe Lewenstein, New results on induced matchings, Discrete Applied Mathematics 101 (2000), 157–165.

    Article  MATH  MathSciNet  Google Scholar 

  11. S. Janson and J. Kratochvil, Threshold functions for classes of intersection graphs, Discrete Mathematics 108 (1992), 307–326.

    Article  MATH  MathSciNet  Google Scholar 

  12. 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.

    Google Scholar 

  13. Alexandr Kostochka and Jan Kratochvíl, Covering and coloring polygon-circle graphs, Discrete Mathematics 163 (1997), 299–305.

    Article  MATH  MathSciNet  Google Scholar 

  14. Michael D. Plummer, Michael Stiebitz and Bjarne Toft, On a special case of Hadwiger’s conjecture, manuscript June 2001.

    Google Scholar 

  15. Larry J. Stockmeyer and Vijay V. Vazirani, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters 15 (1982), 14–19.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Wilfrid Laurier University, N2L 3C5, Waterloo, Ontario, Canada

    Kathie Cameron

Authors
  1. Kathie Cameron
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institut für Informatik, Universität zu Köln, Pohligstr. 1, 50969, Köln, Germany

    Michael Jünger

  2. Institut für Informatik, Universität Heidelberg, Im Neuenheimer Feld 368, 69120, Heidelberg, Germany

    Gerhard Reinelt

  3. Istituto di Analisi dei Sistemi ed Informatica “Antonio Ruberti”, CNR, viale Manzoni 30, 00185, Rome, Italy

    Giovanni Rinaldi

Rights and permissions

Reprints 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

Publish with us

Policies and ethics

Search

Navigation