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

minimum edge cutsweighted undirected graphGomory-Hu cut tree

Mathematics Subject Classification ID

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

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

(10)

• Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions
• Optimal cuts and partitions in tree metrics in polynomial time
• Improved parameterized and exact algorithms for cut problems on trees
• Flow trees for vertex-capacitated networks
• Counterexamples for Directed and Node Capacitated Cut-Trees
• Fast and simple fully-dynamic cut tree construction
• scientific article; zbMATH DE number 1135820 (Why is no real title available?)
• Extracting maximal information about sets of minimum cuts
• Cut tree algorithms: An experimental study
• When do Gomory-Hu subtrees exist?

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)