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