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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth

verfasst von : Martin Dyer, Catherine Greenhill, Haiko Müller

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Glauber dynamics can efficiently sample independent sets almost uniformly at random in polynomial time for graphs in a certain class. The class is determined by boundedness of a new graph parameter called bipartite pathwidth. This result, which we prove for the more general hardcore distribution with fugacity \(\lambda \), can be viewed as a strong generalisation of Jerrum and Sinclair’s work on approximately counting matchings. The class of graphs with bounded bipartite pathwidth includes line graphs and claw-free graphs, which generalise line graphs. We consider two further generalisations of claw-free graphs and prove that these classes have bounded bipartite pathwidth.

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 "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

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 Independent Set Reconfiguration Parameterized by Modular-Width
Nächstes Kapitel Intersection Graphs of Non-crossing Paths
Literatur
1.
Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135, 3–16 (2004)MathSciNetCrossRef
2.
3.
Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: Proceedings of the STOC, pp. 122–127 (2007)
4.
5.
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)MathSciNetCrossRef
6.
Bodlander, H.L.: A partial \(k\)-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1–45 (1998)MathSciNetCrossRef
7.
Chudnovsky, M., Seymour, P.: The roots of the independence polynomial of a clawfree graph. J. Comb. Theory ( Ser. B) 97, 350–357 (2007)MathSciNetCrossRef
8.
Diaconis, P., Saloff-Coste, L.: Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, 696–730 (1993)MathSciNetCrossRef
9.
Diaconis, P., Stroock, D.: Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1, 36–61 (1991)MathSciNetCrossRef
10.
11.
Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: On the relative complexity of approximate counting problems. Algorithmica 38, 471–500 (2003)MathSciNetCrossRef
12.
13.
Dyer, M., Greenhill, C., Müller, H.: Counting independent sets in graphs with bounded bipartite pathwidth. Preprint: arXiv:​1812.​03195 (2018)
14.
Efthymiou, C., Hayes, T., Stefankovic, D., Vigoda, E., Yin, Y.: Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model. In: Proceedings of the FOCS 2016, pp. 704–713. IEEE (2016)
15.
Greenhill, C.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complex. 9, 52–72 (2000)MathSciNetCrossRef
16.
Harvey, N.J.A., Srivastava, P., Vondrák, J.: Computing the independence polynomial: from the tree threshold down to the roots. In: Proceedings of the SODA 2018, pp. 1557–1576 (2018)CrossRef
17.
18.
Jerrum, M.: Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics - ETH Zürich. Birkhäuser, Basel (2003)CrossRef
19.
20.
Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51, 671–697 (2004)MathSciNetCrossRef
21.
Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169–188 (1986)MathSciNetCrossRef
22.
Matthews, J.: Markov chains for sampling matchings, Ph.D. thesis, University of Edinburgh (2008)
23.
Luby, M., Vigoda, E.: Approximately counting up to four. In: Proceedings of the STOC 1995, pp. 150–159. ACM (1995)
24.
Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28, 284–304 (1980)MathSciNetCrossRef
25.
Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46, 1893–1919 (2017)MathSciNetCrossRef
26.
Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12, 777–788 (1983)MathSciNetCrossRef
27.
28.
Sinclair, A.: Improved bounds for mixing rates of Markov chains and multicommodity flow. Comb. Probab. Comput. 1, 351–370 (1992)MathSciNetCrossRef
29.
Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the FOCS 2010, pp. 287–296. IEEE (2010)
30.
Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31, 398–427 (2001)MathSciNetCrossRef
31.
Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the STOC 2006, pp. 140–149. ACM (2006)
Metadaten
Titel
Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth
verfasst von
Martin Dyer
Catherine Greenhill
Haiko Müller
Copyright-Jahr
2019
Buch
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-030-30785-1

Electronic ISBN: 978-3-030-30786-8

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-30786-8_23