Extracting maximal information about sets of minimum cuts

DOI10.1007/BF01908632zbMath0781.90087MaRDI QIDQ1261290

Dalit Naor, Dan Gusfield

Publication date: 1 September 1993

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

directed acyclic graphnetwork reliabilityminimum edge cutsedge-connectivity cutsunweighted graphweighted, undirected graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Connectivity (05C40)

Related Items (6)

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory ⋮ Multiterminal xcut problems ⋮ Compact cactus representations of all non-trivial min-cuts ⋮ On enumerating minimal dicuts and strongly connected subgraphs ⋮ Extracting maximal information about sets of minimum cuts ⋮ An efficient approximation algorithm for the survivable network design problem

Cites Work

• Unnamed Item
• Unnamed Item
• Multi-terminal maximum flows in node-capacitated networks
• An algorithm to generate the ideals of a partial order
• Extracting maximal information about sets of minimum cuts
• A paradigm for listing \((s,t)\)-cuts in graphs
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• Bottlenecks and Edge Connectivity in Unsymmetrical Networks
• On computing the connectivities of graphs and digraphs
• Very Simple Methods for All Pairs Network Flow Analysis
• Calculating bounds on reachability and connectedness in stochastic networks
• Counting almost minimum cutsets with reliability applications
• Three Fast Algorithms for Four Problems in Stable Marriage
• A new approach to the maximum-flow problem
• Finding the edge connectivity of directed graphs
• Solution Bases of Multiterminal Cut Problems
• Multi-Terminal Network Flows
• On the structure of all minimum cuts in a network and applications
• Selected Applications of Minimum Cuts in Networks
• Efficient algorithms for generalized cut‐trees
• The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n‐Bonds
• Network Flow and Testing Graph Connectivity
• A Fast Parametric Maximum Flow Algorithm and Applications

This page was built for publication: Extracting maximal information about sets of minimum cuts