scientific article; zbMATH DE number 177555

MaRDI QIDQ4037426zbMATH OpenFDO

Authors Dalit Naor, Vijay V. Vazirani

Publication date 18 May 1993

zbMATH Keywords

connectivity cutsRNC algorithmundirected edge-weighted graph

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
• scientific article; zbMATH DE number 437525
• Approximating unweighted connectivity problems in parallel
• An \NC Algorithm for Minimum Cuts
• scientific article; zbMATH DE number 1104333

Cited in

(9)

• Canonical cactus representation for miminum cuts
• Generating partitions of a graph into a fixed number of minimum weight cuts
• A fast algorithm for cactus representations of minimum cuts
• Computing finest mincut partitions of a graph and application to routing problems
• Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
• Separating maximally violated comb inequalities in planar graphs
• Computing exact minimum cuts without knowing the graph
• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• The cactus tree of a metric space

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 Q4037426)