Integrating and Sampling Cuts in Bounded Treewidth Graphs

DOI10.1007/978-3-319-34139-2_20zbMath1350.05157OpenAlexW2508460026MaRDI QIDQ2833051

Kyle Fox, Ivona Bezáková, Erin Wolf Chambers

Publication date: 16 November 2016

Published in: Association for Women in Mathematics Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-34139-2_20

zbMATH Keywords

algorithmstreewidthminimum cuts

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts

Cites Work

• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Graph minors. III. Planar tree-width
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Combinatorial aspects of network reliability
• S-functions for graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Calculating bounds on reachability and connectedness in stochastic networks
• Complexity of Finding Embeddings in a k-Tree
• Counting the number of minimum cuts in undirected multigraphs
• Counting and sampling minimum cuts in genus g graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item