Efficient algorithms for generalized cut‐trees

DOI10.1002/NET.3230210503MaRDI QIDQ3978604zbMATH OpenOpenAlexFDO

Authors Dalit Naor, Dan Gusfield

Publication date 25 June 1992

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230210503

zbMATH Keywords

Gomory-Hu cut treeminimum edge cutsweighted undirected graph

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1305427
• Compact representations of cuts
• Extracting maximal information about sets of minimum cuts

Cites work

• scientific article; zbMATH DE number 3441964 (Why is no real title available?)
• scientific article; zbMATH DE number 3314878 (Why is no real title available?)
• On the structure of all minimum cuts in a network and applications

Cited in

(16)

• Ancestor tree for arbitrary multi-terminal cut functions
• Extracting maximal information about sets of minimum cuts
• Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions
• Cut tree algorithms: An experimental study
• A Gomory-Hu cut tree representation of a netlist partitioning problem
• Optimal cuts and partitions in tree metrics in polynomial time
• scientific article; zbMATH DE number 1305427 (Why is no real title available?)
• scientific article; zbMATH DE number 1135820 (Why is no real title available?)
• Counterexamples for Directed and Node Capacitated Cut-Trees
• Fast and simple fully-dynamic cut tree construction
• When do Gomory-Hu subtrees exist?
• A cut tree representation for pendant pairs
• Space complexity of vertex connectivity oracles
• Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
• Flow trees for vertex-capacitated networks
• Improved parameterized and exact algorithms for cut problems on trees

This page was built for publication: Efficient algorithms for generalized cut‐trees

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