Integrating and sampling cuts in bounded treewidth graphs

DOI10.1007/978-3-319-34139-2_20MaRDI QIDQ2833051zbMATH OpenOpenAlexFDO

Authors Ivona Bezáková, Kyle Fox, Erin W. 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

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

Recommendations

• Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
• Approximating sparsest cut in graphs of bounded treewidth
• Minimum cuts in near-linear time
• Random sampling in cut, flow, and network design problems
• Graph-Theoretic Concepts in Computer Science

Cites work

• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 1263176 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximate counting, uniform generation and rapidly mixing Markov chains
• 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
• Combinatorial aspects of network reliability
• Complexity of Finding Embeddings in a k-Tree
• Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
• Counting and sampling minimum cuts in genus g graphs
• Counting the number of minimum cuts in undirected multigraphs
• Graph minors. III. Planar tree-width
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• S-functions for graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(1)

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

This page was built for publication: Integrating and sampling cuts in bounded treewidth graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2833051)