scientific article; zbMATH DE number 1263227

MaRDI QIDQ4234099zbMATH OpenFDO

Authors Zeev Nutov, Yefim Dinitz

Publication date 29 January 2002

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A near-linear time algorithm for constructing a cactus representation of minimum cuts
• A fast algorithm for cactus representations of minimum cuts
• CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
• Incremental algorithm for minimum cut and edge connectivity in hypergraph
• Compact cactus representations of all non-trivial min-cuts
• Cactus graphs with minimum edge revised Szeged index
• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• Minimal cuts in two-terminal directed acyclic graphs
• On computing minimum(s,t)-cuts in digraphs
• Mincut Sensitivity Data Structures for the Insertion of an Edge

Cited in

(22)

• Phylogenetic graph models beyond trees
• How to draw the minimum cuts of a planar graph
• Approximation algorithms for connectivity augmentation problems
• 2-node-connectivity network design
• Connectivity oracles for graphs subject to vertex failures
• scientific article; zbMATH DE number 2044925 (Why is no real title available?)
• The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case
• Approximating minimum cuts under insertions
• 2-node-connectivity network design
• Improved approximations for relative survivable network design
• Approximation algorithms for node and element connectivity augmentation problems
• Space complexity of vertex connectivity oracles
• Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
• Improved approximation algorithms for covering pliable set families and flexible graph connectivity
• Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
• The structure of minimum vertex cuts
• Parameterized algorithms for node connectivity augmentation problems
• Optimal sensitivity oracle for Steiner mincut
• On maximal k-edge-connected subgraphs of undirected graphs
• Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut
• Minimum+1 Steiner cut and dual edge sensitivity oracle: bridging gap between global and (s,t)-cut
• On the structure of vertex cuts separating the ends of a graph

This page was built for publication:

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