nach oben

Erschienen in:

2013 | OriginalPaper | Buchkapitel

Maximum Induced Matchings in Grids

verfasst von : Ruxandra Marinescu-Ghemeci

Erschienen in: Optimization Theory, Decision Making, and Operations Research Applications

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

An induced matching in a graph is a matching such that no two edges are joined by an edge of G. For a connected graph G, denote by iμ(G) the maximum cardinality of an induced matching in G. In this paper we study the proble of finding a maximum induced matching in grid graphs with n lines and m columns—G _{n, m}, and determine the exact value for iμ(G _{n, m}) when n or m are even.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Parallel Implementation of the Revised Simplex Algorithm Using OpenMP: Some Preliminary Results

Nächstes Kapitel Determining the Minimum Number of Warehouses and their Space-Size for Storing Compatible Items

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., and Stougie, L.: Minimizing flow time in the wireless gathering problem. ACM Transactions on Algorithms7(3), (2011) http://arxiv.org/abs/0802.2836.

Cameron, K.: Induced matchings. Discrete Appl. Math. 24, 97–102 (1989)MATHCrossRef

Cameron, K.: Induced matchings in intersection graphs. Discrete Math. 278, 1–9 (2004)MathSciNetMATHCrossRef

Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math. 266, 133–142 (2003)MathSciNetMATHCrossRef

Dabrowski, K., Demange, M., and Lozin, V.V.: New results on maximum induced matchings in bipartite graphs and beyond. submitted, http://homepages.warwick.ac.uk/~mariaq/

Faudree, R.J., Gyárfas, A., Schelp, R.H., Tuza, Z.: Induced matchings in bipartite graphs. Discrete Math. 78, 83–87 (1989)MathSciNetMATHCrossRef

Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Appl. Math. 101, 157–165 (2000)MathSciNetMATHCrossRef

Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and P5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327–346 (2003)MathSciNetMATHCrossRef

Lozin, V.V.: On maximum induced matchings in bipartite graphs. Inform. Process. Lett. 81 7–11 (2002)MathSciNetMATHCrossRef

10.

Rusu, I.: Maximum weight edge-constrained matchings. Discrete Appl. Math. 156, 662–672 (2008)MathSciNetMATHCrossRef

11.

Stockmeyer, L.J., Vazirani, V.V.: Np-completeness of some generalizations of the maximum matching problem. I.P.L. 15, 14–19 (1982)

Titel: Maximum Induced Matchings in Grids
verfasst von: Ruxandra Marinescu-Ghemeci
Verlag: Springer New York
Buch: Optimization Theory, Decision Making, and Operations Research Applications
Print ISBN: 978-1-4614-5133-4

Electronic ISBN: 978-1-4614-5134-1

Copyright-Jahr: 2013
DOI: https://doi.org/10.1007/978-1-4614-5134-1_12