Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
type: Item
instance of: scholarly article
title: Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
zbMATH Open document ID: 1236.05066
author: Ivona Bezáková
author: Adam J. Friedlander
published in: Theoretical Computer Science
publication date: 2012-03-13T00:00:00Z
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68U10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6014312
zbMATH Keywords: counting and sampling
zbMATH Keywords: minimum \((s,t)\)-cuts
zbMATH Keywords: weighted planar graphs
zbMATH Keywords: maximum flow
zbMATH Keywords: maximal antichains in partially ordered sets
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.05.017
OpenAlex ID: W2049188514
cites work: Calculating bounds on reachability and connectedness in stochastic networks
cites work: Computing Network Reliability in Time Polynomial in the Number of Cuts
cites work: An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
cites work: Combinatorial aspects of network reliability
cites work: Introduction to algorithms
cites work: Maximal Flow Through a Network
cites work: A new approach to the maximum-flow problem
cites work: Efficient Planarity Testing
cites work: Maximum Flow in Planar Networks
cites work: Q4008192
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
cites work: Counting the number of minimum cuts in undirected multigraphs
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: Counting almost minimum cutsets with reliability applications
cites work: Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
DOI: 10.1016/J.TCS.2011.05.017
description: scientific article; zbMATH DE number 6014312