Counterexamples for Directed and Node Capacitated Cut-Trees

DOI10.1137/S0097539792236730MaRDI QIDQ4842118zbMATH OpenWikidataFDO

Authors András A. Benczúr

Publication date 18 March 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539792236730

zbMATH Keywords

connectivitycut-treedirected Eulerian graphsminimum cuts

Mathematics Subject Classification ID

Connectivity (05C40) Deterministic network models in operations research (90B10)

Recommendations

• Efficient algorithms for generalized cut‐trees
• Compact representations of cuts
• Extracting maximal information about sets of minimum cuts
• Cut tree algorithms: An experimental study
• Excluding a simple good pair approach to directed cuts

Cited in

(17)

• Greedy splitting algorithms for approximating multiway partition problems
• Revisiting parametric multi-terminal problems: maximum flows, minimum cuts and cut-tree computations
• Efficient algorithm for computing all low s-t edge connectivities in directed graphs
• Tight Bounds for Gomory-Hu-like Cut Counting
• On element-connectivity preserving graph simplification
• scientific article; zbMATH DE number 1154595 (Why is no real title available?)
• Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
• Strong connectivity in directed graphs under failures, with applications
• Faster algorithms for shortest path and network flow based on graph decomposition
• Empirical study on sufficient numbers of minimum cuts in strongly connected directed random graphs
• Tight conditional lower bounds for vertex connectivity problems
• Space complexity of vertex connectivity oracles
• The structure of minimum vertex cuts
• Higher connectivity in directed graphs (invited talk)
• An efficient algorithm for computing average network flow
• Flow equivalent trees in undirected node-edge-capacitated planar graphs
• Flow trees for vertex-capacitated networks

This page was built for publication: Counterexamples for Directed and Node Capacitated Cut-Trees

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