Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 3/2016

01.10.2016

Counting the Number of Perfect Matchings in K 5-Free Graphs

verfasst von: Simon Straub, Thomas Thierauf, Fabian Wagner

Erschienen in: Theory of Computing Systems | Ausgabe 3/2016

Einloggen

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

search-config
loading …

Abstract

Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K 3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K 5-free graphs, this technique will not work because some K 5-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K 5-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC2. We remark that our results generalize to graphs without singly-crossing minor.
Vorheriger Artikel Network Formation for Asymmetric Players and Bilateral Contracting
Nächster Artikel Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness

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

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Barahona, F.: Balancing signed toroidal graphs in polynomial time. Technical report, University of Chile (1983)
2.
Di Battista, G., Tamassia, R.: Incremental planarity testing. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 436–441 (1989)
3.
Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15(4), 302–318 (1996)MathSciNetCrossRefMATH
4.
Cayley, A.: Sur les déterminants gauches. J. Pure Appl. Math. 38, 93–96 (1847)MathSciNet
5.
Curticapean, R.: Counting perfect matchings in graphs that exclude a single-crossing minor. arXiv:1406.​4056 (2014)
6.
Demaine, E.D., Hajiaghayi, M., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2), 166–195 (2004)MathSciNetCrossRefMATH
7.
Datta, S., Nimbhorkar, P., Thierauf, T., Wagner, F.: Isomorphism for K 3,3-free and K 5-free graphs is in log-space. In: Proceedings of the 29th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 145–156 (2009)
8.
9.
Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle. In: 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 143–152 (2010)
10.
11.
Gibbons, A., Rytter, W.: Efficient Parallel Algorithms. Cambridge University Press, Cambridge (1988)MATH
12.
Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)MATH
13.
Hopcroft, J.E., Tarjan, R.E.: A \(V\log V\) algorithm for isomorphism of triconnected planar graphs. J. Comput. Syst. Sci. 7 (3), 323–331 (1973)MathSciNetCrossRefMATH
14.
Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp 43–110. Academic, New York (1967)
15.
Kulkarni, R., Mahajan, M., Varadarajan, K.: Some perfect matchings and perfect half-integral matchings in NC. Chic. J. Theor. Comput. Sci. 2008(4), 1–26 (2008)MathSciNetCrossRefMATH
16.
Kuratowski, K.: Sur le probléme des courbes gauches en topologie. Fundam. Math. 15, 271–283 (1930)MATH
17.
Little, C.H.C.: An extension of Kasteleyn’s method of enumerating the 1-factors of planar graphs. In: Holton, D.A. (ed.) Combinatorial Mathematics, volume 403 of Lecture Notes in Mathematics, pp 63–72. Springer, Berlin Heidelberg (1974)
18.
Miller, G.L., Ramachandran, V.: A new graph triconnectivity algorithm and its parallelization. Combinatorica 12, 53–76 (1992)MathSciNetCrossRefMATH
19.
Mahajan, M., Subramanya, P.R., Vinay, V.: The combinatorial approach yields an NC algorithm for computing Pfaffians. Discrete Appl. Math. 143(1–3), 1–16 (2004)MathSciNetCrossRefMATH
20.
Robertson, N., Seymour, P.: Excluding a graph with one crossing. In: Graph Structure Theory, pp. 669–675. American Mathematical Society (1993)
21.
Tutte, W.T.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)MATH
22.
Thierauf, T., Wagner, F.: Reachability in K 3,3-free graphs and K 5-free graphs is in unambiguous log-space. Chic. J. Theor. Comput. Sci., To appear (2014)
23.
24.
25.
Vazirani, V.: NC algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems. Inf. Comput. 80(2), 152–164 (1989)MathSciNetCrossRefMATH
26.
27.
Metadaten
Titel
Counting the Number of Perfect Matchings in K 5-Free Graphs
verfasst von
Simon Straub
Thomas Thierauf
Fabian Wagner
Publikationsdatum
01.10.2016
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 3/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-015-9645-1

Weitere Artikel der Ausgabe 3/2016

Theory of Computing Systems 3/2016 Zur Ausgabe

OriginalPaper

On the Minimization of (Complete) Ordered Binary Decision Diagrams

OriginalPaper

Distinguishing Two Probability Ensembles with One Sample from each Ensemble

OriginalPaper

Learning Sets of Antecedent-restricted Functional and Multivalued Dependencies with Queries

OriginalPaper

Assignment Games with Conflicts: Robust Price of Anarchy and Convergence Results via Semi-Smoothness

OriginalPaper

On the Advice Complexity of the k-server Problem Under Sparse Metrics

OriginalPaper

Network Formation for Asymmetric Players and Bilateral Contracting

Premium Partner

    Bildnachweise