Counting and sampling minimum cuts in genus g graphs

DOI10.1145/2462356.2462366MaRDI QIDQ5174485zbMATH OpenOpenAlexFDO

Authors Kyle Fox, Amir Nayyeri, Erin W. Chambers

Publication date 17 February 2015

Published in Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2462356.2462366

zbMATH Keywords

computational topologyminimum cutstopological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Counting and sampling minimum cuts in genus g graphs
• Counting and sampling minimum (s,t)-cuts in weighted planar graphs in polynomial time
• Counting the number of minimum cuts in undirected multigraphs
• scientific article; zbMATH DE number 2089977
• On the Number of Minimum Cuts in a Graph
• On minimal cuts of recursively generated hypergraphs
• scientific article; zbMATH DE number 5823703
• Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time
• scientific article; zbMATH DE number 1234600

Cited in

(5)

• Fixed-parameter tractability of counting small minimum \((S,T)\)-cuts
• Integrating and sampling cuts in bounded treewidth graphs
• Counting and sampling minimum cuts in genus g graphs
• Global minimum cuts in surface embedded graphs
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts

This page was built for publication: Counting and sampling minimum cuts in genus g graphs

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