On the structure of all minimum cuts in a network and applications
From MaRDI portal
Publication:3885550
DOI10.1007/BFB0120902zbMath0442.90093OpenAlexW4234163381MaRDI QIDQ3885550
Jean-Claude Picard, Maurice Queyranne
Publication date: 1980
Published in: Mathematical Programming Studies (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bfb0120902
sensitivityproject selectionenumerationmaximum flowvertex packingfinite directed networkmaximum closure problemsparametric analyses of networkspositive arc capacitiesstructure of all minimum cutsunconstrained pseudo-boolean optimization
Related Items (44)
Parametric maximum flow methods for minimax approximation of target quotas in biproportional apportionment ⋮ An algorithm to generate the ideals of a partial order ⋮ On computing minimum\((s,t)\)-cuts in digraphs ⋮ A compact representation for minimizers of \(k\)-submodular functions ⋮ Maximizing residual flow under an arc destruction ⋮ Efficient algorithms for generalized cut‐trees ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Menger-decomposition of a graph and its application to the structural analysis of a large-scale system of equations ⋮ Separation, dimension, and facet algorithms for node flow polyhedra ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Mincut sensitivity data structures for the insertion of an edge ⋮ The maximum flow problem with disjunctive constraints ⋮ Threshold reliability of networks with small failure sets ⋮ \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time ⋮ Submodular reassignment problem for reallocating agents to tasks with synergy effects ⋮ Lexicographically optimal earliest arrival flows ⋮ On the minimum \(s-t\) cut problem with budget constraints ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Unnamed Item ⋮ Theory of Principal Partitions Revisited ⋮ A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time ⋮ Fair-by-design matching ⋮ Mincut Sensitivity Data Structures for the Insertion of an Edge ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Optimal cuts in graphs and statistical mechanics ⋮ Most balanced minimum cuts ⋮ A fast algorithm for cactus representations of minimum cuts ⋮ An efficient network flow code for finding all minimum cost \(s-t\) cutsets ⋮ Suboptimal cuts: Their enumeration, weight and number ⋮ Representation of lattices via set-colored posets ⋮ Extracting maximal information about sets of minimum cuts ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Structural theorems for submodular functions, polymatroids and polymatroid intersections ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract) ⋮ Boolean sublattices connected with minimization problems on matroids ⋮ An efficient approximation algorithm for the survivable network design problem ⋮ A dynamic graph characterisation of the fixed part of the controllable subspace of a linear structured system ⋮ Discrete Newton methods for the evacuation problem ⋮ Ordered optimal solutions and parametric minimum cut problems ⋮ Characterization of all optimal solutions and parametric maximal mows in networks ⋮ Finding all minimum-size separating vertex sets in a graph ⋮ Polyhedral computational geometry for averaging metric phylogenetic trees ⋮ Calculating bounds on reachability and connectedness in stochastic networks ⋮ Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
This page was built for publication: On the structure of all minimum cuts in a network and applications
