nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Integrating and Sampling Cuts in Bounded Treewidth Graphs

verfasst von : Ivona Bezáková, Erin W. Chambers, Kyle Fox

Erschienen in: Advances in the Mathematical Sciences

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we consider the problem of evaluating (s, t)-cuts in a bounded treewidth graph. In particular, we show how to compute the partition function for weighted cuts of the graph, i.e., the total weight of all (s, t)-cuts where the weight of a single cut is the product of its edge weights. This method can also easily be adapted to work with additive weights for the cost of a cut. We also present a method for sampling a cut proportional to its weight in linear time. Computing the partition function is #P-hard for general graphs, and our sampling algorithm is simple enough to prove useful is several application areas. Finally, we discuss an alternative method for sampling cuts that uses Markov chains and show that, in the worst case, its mixing time is exponential in the size of the graph even when the graph has bounded treewidth.

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 Information Measures of Frequency Distributions with an Application to Labeled Graphs

Nächstes Kapitel Considerations on the Implementation and Use of Anderson Acceleration on Distributed Memory and GPU-based Parallel Computers

S. Arnborg, D. Corneil, A. Proskurowski, Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discret. Methods 8(2), 277–284 (1987). http://epubs.siam.org/doi/abs/10.1137/0608024

M.O. Ball, S.J. Provan, Calculating bounds on reachability and connectedness in stochastic networks. Networks 13, 253–278 (1983)MathSciNetCrossRefMATH

I. Bezáková, A.J. Friedlander, Counting and sampling minimum \((s, t)\)-cuts in weighted planar graphs in polynomial time. Theoret. Comput. Sci. 417, 2–11 (2012)MathSciNetCrossRefMATH

H. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996). http://epubs.siam.org/doi/abs/10.1137/S0097539793251219

H.L. Bodlaender, Dynamic programming on graphs with bounded treewidth, in Automata, Languages and Programming, vol. 317, Lecture Notes in Computer Science, ed. by T. Lepistö, A. Salomaa (Springer, Berlin, 1988), pp. 105–118

Y. Boykov, O. Veksler, Graph cuts in vision and graphics: theories and applications, in Handbook of Mathematical Models in Computer Vision, ed. by N. Paragios, Y. Chen, O. Faugeras (Springer, New York, 2006), pp. 79–96

E.W. Chambers, K. Fox, A. Nayyeri, Counting and sampling minimum cuts in genus g graphs, in Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry, SoCG ’13, ACM, New York, NY, USA (2013), pp. 249–258. http://doi.acm.org/10.1145/2462356.2462366

C.J. Colbourn, Combinatorial aspects of network reliability. Ann. Oper. Res. 33, 1–15 (1991)MathSciNetCrossRefMATH

B. Courcelle, The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85, 12–75 (1990)MathSciNetCrossRefMATH

10.

B. Courcelle, J. Makowsky, U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discret. Appl. Math. 108(1–2), 23–52 (2001). http://www.sciencedirect.com/science/article/pii/S0166218X00002213 (Workshop on Graph Theoretic Concepts in Computer Science)

11.

M. Grohe, Algorithmic meta theorems, in Graph-Theoretic Concepts in Computer Science, vol. 5344, Lecture Notes in Computer Science, ed. by H. Broersma, T. Erlebach, T. Friedetzky, D. Paulusma (Springer, Berlin, 2008), pp. 30–30

12.

R. Halin, S-functions for graphs. J. Geom. 8(1–2), 171–186 (1976). http://dx.doi.org/10.1007/BF01917434

13.

M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics. ETH Zürich. (Springer, New York, 2003). http://books.google.com/books?id=aLINQMsDQQ0C

14.

D.R. Karger, A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, ACM, New York, NY, USA, (1995), pp. 11–17

15.

G. Lawler, A. Sokal, Bounds on the l2 spectrum for Markov chains and markov processes: a generalization of Cheeger’s inequality. Trans. Am. Math. Soc. 309, 557–580 (1988)MathSciNetMATH

16.

H. Nagamoch, Z. Sun, T. Ibaraki, Counting the number of minimum cuts in undirected multigraphs. IEEE Trans. Reliab. 40, 610–614 (1991)CrossRefMATH

17.

S.J. Provan, M.O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12, 777–788 (1983)MathSciNetCrossRefMATH

18.

N. Robertson, P. Seymour, Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49–64 (1984). http://www.sciencedirect.com/science/article/pii/0095895684900133

19.

A. Sinclair, M. Jerrum, Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput. 82(1), 93–133 (1989)MathSciNetCrossRefMATH

Titel: Integrating and Sampling Cuts in Bounded Treewidth Graphs
verfasst von: Ivona Bezáková
Erin W. Chambers
Kyle Fox
Verlag: Springer International Publishing
Buch: Advances in the Mathematical Sciences
Print ISBN: 978-3-319-34137-8

Electronic ISBN: 978-3-319-34139-2

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-34139-2_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner