A Fast Parametric Maximum Flow Algorithm and Applications
From MaRDI portal
Publication:4729349
DOI10.1137/0218003zbMath0679.68080OpenAlexW2013469283MaRDI QIDQ4729349
Giorgio Gallo, Robert Endre Tarjan, Michael D. Grigoriadis
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218003
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items
A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards, Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search, Space-sweep algorithms for parametric optimization, Parametric problems on graphs of bounded tree-width, Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry, On the Implementation of Combinatorial Algorithms for the Linear Exchange Market, Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset, Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs, The minimum color sum of bipartite graphs, Computing Behavioral Relations for Probabilistic Concurrent Systems, Finding dense subgraphs with maximum weighted triangle density, Complexity of source-sink monotone 2-parameter min cut, On the Complexity of Hub Labeling (Extended Abstract), Generalized max flows and augmenting paths, Maximum flows in parametric graph templates, Optimal hierarchical clustering on a graph, Lexicographically optimal earliest arrival flows, Applications and efficient algorithms for integer programming problems on monotone constraints, In search of dense subgraphs: How good is greedy peeling?, Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint, On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition, Covering a graph with densest subgraphs, Parametric matroid interdiction, Deciding Simulations on Probabilistic Automata, A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems, Theory of Principal Partitions Revisited, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Unnamed Item, Adjacency-Clustering and Its Application for Yield Prediction in Integrated Circuit Manufacturing, Machine Speed Scaling by Adapting Methods for Convex Optimization with Submodular Constraints, A Space-Efficient Probabilistic Simulation Algorithm, Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach, Contrasting the Spread of Misinformation in Online Social Networks, A stronger lower bound on parametric minimum spanning trees, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Universally maximum flow with piecewise-constant capacities, An introduction to continuous optimization for imaging, Parametric Power Supply Networks, A branch-and-bound algorithm for multi-dimensional quadratic 0–1 knapsack problems, A fast parametric assignment algorithm with applications in max-algebra, Total Variation in Imaging, Unnamed Item, Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines, Unnamed Item, High-confidence estimation of small s -t reliabilities in directed acyclic networks, Summary and Semi-average Similarity Criteria for Individual Clusters, EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS, Distributed Spanner Approximation, GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE, Parametric Shortest-Path Algorithms via Tropical Geometry, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering, Complexity of finding dense subgraphs, Stackelberg bipartite vertex cover and the preflow algorithm, Computing maximum mean cuts, An FPTAS for the parametric knapsack problem, Parametric max flow problems in a class of networks with series-parallel structure, Improved balanced flow computation using parametric flow, Strengthening ties towards a highly-connected world, Multicommodity flows over time: Efficient algorithms and complexity, Dynamic expression trees, Energy optimal schedules for jobs with multiple active intervals, A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows, Preemptive benchmarking problem: An approach for official statistics in small areas, Strength of a graph and packing of trees and branchings, On total variation minimization and surface evolution using parametric maximum flows, A faster algorithm for computing the principal sequence of partitions of a graph, An efficient algorithm for solving pseudo clique enumeration problem, Image restoration with discrete constrained total variation. I: Fast and exact optimization, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, An approximation algorithm for a general class of parametric optimization problems, Optimization of computations, Minimum cuts in parametric networks, A solution to the random assignment problem on the full preference domain, HNCcorr: combinatorial optimization for neuron identification, Integral packing of trees and branchings, Maximal closure on a graph with resource constraints, On strongly polynomial dual simplex algorithms for the maximum flow problem, How to compute least infeasible flows, Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering, The quadratic knapsack problem -- a survey, Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost, Estimating piecewise monotone signals, A parametric maximum flow algorithm for bipartite graphs with applications, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Equivalence of convex minimization problems over base polytopes, Branch-and-mincut: global optimization for image segmentation with high-level priors, A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem, On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems, Domain decomposition methods with graph cuts algorithms for total variation minimization, A push-relabel framework for submodular function minimization and applications to parametric optimization, Improving graph partitions using submodular functions., Parametric stable marriage and minimum cuts, Fair-by-design matching, Precedence constrained scheduling to minimize sum of weighted completion times on a single machine, Graph clustering, Exact algorithms for problems related to the densest \(k\)-set problem, A note on balanced flows in equality networks, A polynomial time algorithm for the minimum flow problem in time-varying networks, Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs, Forests, frames, and games: Algorithms for matroid sums and applications, A fast algorithm for the generalized parametric minimum cut problem and applications, Polynomial-time algorithms for submodular Laplacian systems, Constrained 0-1 quadratic programming: basic approaches and extensions, Polynomiality of sparsest cuts with fixed number of sources, Approximation schemes for the parametric knapsack problem, Dynamic evolution of economically preferred facilities, Transitions in geometric minimum spanning trees, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, A note on the parametric maximum flow problem and some related reoptimization issues, Complexity and algorithms for nonlinear optimization problems, Generalization of a theorem on the parametric maximum flow problem, An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths, In search of the densest subgraph, Computer science and decision theory, Structural and algorithmic properties for parametric minimum cuts, The complexity of detecting fixed-density clusters, Network flow approaches to pre-emptive open-shop scheduling problems with time-windows, Approximating the Minimum Chain Completion problem, Submodular function minimization, A survey on models and algorithms for discrete evacuation planning network problems, An FPTAS for the knapsack problem with parametric weights, Towards equitable distribution via proportional equity constraints, The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths, Evaluating performance of image segmentation criteria and techniques, A new upper bound for the 0-1 quadratic knapsack problem, Extracting maximal information about sets of minimum cuts, Parametric min-cuts analysis in a network., Computing the binding number of a graph, Linear programming for the \(0-1\) quadratic knapsack problem, Lagrangean methods for the 0-1 quadratic knapsack problem, Optimal location with equitable loads, On the supermodular knapsack problem, Diagnosing infeasibilities in network flow problems, An approximation algorithm for a general class of multi-parametric optimization problems, Submodular optimization views on the random assignment problem, Ordered optimal solutions and parametric minimum cut problems, Computing the \(k\) densest subgraphs of a graph, Minimizing a submodular function arising from a concave function, Parametric analysis of overall min-cuts and applications in undirected networks., On some algorithmic aspects of hypergraphic matroids, Network reinforcement, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, Baseball playoff eliminations: An application of linear programming. Erratum, A note on optimal covering augmentation for graphic polymatroids., A faster parametric minimum-cut algorithm, Algorithms and complexity analysis for some flow problems, A faster algorithm for computing the strength of a network, Parametric power supply networks, An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
