Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
From MaRDI portal
Publication:4080986
DOI10.1145/321694.321699zbMath0318.90024OpenAlexW2149342630WikidataQ29039326 ScholiaQ29039326MaRDI QIDQ4080986
Publication date: 1972
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321694.321699
Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)
Related Items
Maximum and optimal 1-2 matching problem of the different kind, Unnamed Item, Recent developments in maximum flow algorithms, An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications, A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, Unnamed Item, An improved algorithm for reliability bounds of multistate networks, Unnamed Item, Quantifying Statistical Interdependence by Message Passing on Graphs—Part II: Multidimensional Point Processes, Team Orienteering with Time-Varying Profit, TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration, Fair Division of Indivisible Goods for a Class of Concave Valuations, Hypergraph Cuts with General Splitting Functions, On implementing push-relabel method for the maximum flow problem, Generalized max flows and augmenting paths, How hard is safe bribery?, Matching cells, Hedonic diversity games: a complexity picture with more than two colors, Characterization of random walks on space of unordered trees using efficient metric simulation, Fast primal-dual update against local weight update in linear assignment problem and its application, ReLU neural networks of polynomial size for exact maximum flow computation, On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems, An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems, Exact Solution Algorithms for the Chordless Cycle Problem, Maximum skew-symmetric flows, 0/1-Integer programming: Optimization and Augmentation are equivalent, Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs, PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem, A survey on exact algorithms for the maximum flow and minimum‐cost flow problems, Methods for the graph realization problem, Two-Machine and Two-Agent Flow Shop with Special Processing Times Structures, Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages, Unnamed Item, Unnamed Item, Enumerating dissimilar minimum cost perfect and error-correcting bipartite matchings for robust data matching, A new maximal flow algorithm for solving optimization problems with linguistic capacities and flows, Disjoint paths in a network, Cutsets and partitions of hypergraphs, Unnamed Item, A self-stabilizing algorithm for the maximum flow problem, Algorithms, Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs., The computational complexity of optimal blocking of vertices in the digraph, An efficient scaling procedure for gain networks, A submodular optimization problem with side constraints, Unnamed Item, A simple GAP-canceling algorithm for the generalized maximum flow problem, On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds, A fuzzy max-flow min-cut theorem., The complexity of linear programming, The complexity of linear programming, Fast augmentation algorithms for maximising the output flow in repairable flow networks after edge failures, A good algorithm for lexicographically optimal flows in multi-terminal networks, Unnamed Item, Cost operator algorithms for the transportation problem, More pathological examples for network flow problems, Vertex deletion into bipartite permutation graphs, AO(nm log(U/n)) time maximum flow algorithm, A strongly polynomial time algorithm for a constrained submodular optimization problem, Computing a maximum clique in geometric superclasses of disk graphs, Unnamed Item, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, Improving the approximation ratio for capacitated vehicle routing, Approximating the discrete time-cost tradeoff problem with bounded depth, Min-Cost Flow in Unit-Capacity Planar Graphs, Modular circulation and applications to traffic management, Close-to-optimal algorithm for rectangular decomposition of 3D shapes, Optimal project compression with due-dated events, A polynomial time algorithm for cyclic vertex connectivity of cubic graphs, On fair division for indivisible items, BRIDGE LANE DIRECTION SPECIFICATION FOR SUSTAINABLE TRAFFIC MANAGEMENT, On Mergings in Acyclic Directed Graphs, Maximum weightk-independent set problem on permutation graphs, Unnamed Item, The effectiveness of finite improvement algorithms for finding global optima, Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models, Faster algorithms for shortest path and network flow based on graph decomposition, The Recognition Problem of Graph Search Trees, Activity selection games and the minimum‐cut problem, Polynomial algorithms for a class of linear programs, The integer {k}-domination number of circulant graphs, Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors, Combinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow, Unnamed Item, Balanced and Approximate Zero-Variance Recursive Estimators for the Network Reliability Problem, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning, A bad network problem for the simplex method and other minimum cost flow algorithms, An introduction to parallelism in combinatorial optimization, Stackelberg bipartite vertex cover and the preflow algorithm, A strongly polynomial minimum cost circulation algorithm, Scaling algorithms for network problems, A shortest augmenting path algorithm for dense and sparse linear assignment problems, Generalized disk graphs, Euclidean maximum matchings in the plane -- local to global, Maximum likelihood analysis of the Ford-Fulkerson method on special graphs, Fast computation of bounds for two-terminal network reliability, Approximation algorithms for solving the constrained arc routing problem in mixed graphs, Optimal cost sharing for capacitated facility location games, Algorithms for finding k-best perfect matchings, A fast work function algorithm for solving the \(k\)-server problem, A very personal reminiscence on the problem of computational complexity, Quick max-flow algorithm, Primal-dual algorithms for the assignment problem, On the hardness of bribery variants in voting with CP-nets, Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems, Scheduling jobs with fixed start and end times, The data transfer problem in a system of systems, An application of simultaneous diophantine approximation in combinatorial optimization, River routing in VLSI, Constructing a perfect matching is in random NC, Improved bounds for large scale capacitated arc routing problem, Local search heuristics for the mobile facility location problem, An extension of the König-Egerváry property to node-weighted bidirected graphs, Time constrained maximal covering salesman problem with weighted demands and partial coverage, A computational study of efficient shortest path algorithms, Topology optimisation of repairable flow networks for a maximum average availability, Dual coordinate step methods for linear network flow problems, A new algorithm for the directed Chinese postman problem, Subspaces with well-scaled frames, Towards an optimization theory for deforming dense granular materials: minimum cost maximum flow solutions, Penelope's graph: a hard minimum cost tension instance, A parametric maximum flow algorithm for bipartite graphs with applications, Algebraic flows in regular matroids, Uncertain minimum cost flow problem, Simplifying maximum flow computations: the effect of shrinking and good initial flows, Maximum likelihood estimation of Gaussian mixture models using stochastic search, An \(O(EV\log^2V)\) algorithm for the maximal flow problem, An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem, Minimal-cost network flow problems with variable lower bounds on arc flows, On shortest disjoint paths in planar graphs, On the theoretical efficiency of various network flow algorithms, A parallel algorithm for eliminating cycles in undirected graphs, Efficient methods for selfish network design, An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem, A generalized bi-criteria fuzzy integer flow sharing problem, On maximum flows in polyhedral domains, A min-flow algorithm for minimal critical set detection in resource constrained project scheduling, Retiming synchronous circuitry, Selfish splittable flows and NP-completeness, Updating network flows given multiple, heterogeneous arc attribute changes, Selecting a discrete portfolio, About the minimum mean cycle-canceling algorithm, A new approach for solving the network problems, Campaign management under approval-driven voting rules, A genuinely polynomial primal simplex algorithm for the assignment problem, Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors, A scaling technique for finding the weighted analytic center of a polytope, An exterior simplex type algorithm for the minimum cost network flow problem, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Using combinatorial optimization in model-based trimmed clustering with cardinality constraints, My experiences as a student and researcher in OR during the 1960's and 70's, Non-standard approaches to integer programming, Maximum bipartite flow in networks with adaptive channel width, Popular mixed matchings, Chips on wafers, or packing rectangles into grids, Bottleneck flows in unit capacity networks, Due dates assignment and JIT scheduling with equal-size jobs, A new strategy for the undirected two-commodity maximum flow problem, Parallel algorithms for bipartite matching problems on distributed memory computers, Comparing universal covers in polynomial time, Polymatroidal flows with lower bounds, Minimizing mean weighted execution time loss on identical and uniform processors, A min-max relation for stable sets in graphs with no odd-\(K_ 4\), Partial-matching RMS distance under translation: combinatorics and algorithms, Maximizing network throughput under stochastic user equilibrium with elastic demand, Submodular function minimization, A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time, Approximate labelled subtree homeomorphism, A polynomial algorithm for minimum quadratic cost flow problems, Finding optimal paths in MREP routing, Maximum weight bipartite matching in matrix multiplication time, An approach to the parallel solution of a high-dimensional basic flow problem, The attractive traveling salesman problem, Recent trends in combinatorial optimization, A solution method for the non-additive resource allocation problem in distributed system design, The optimum assignments and a new heuristic approach for the traveling salesman problem, Testing membership in matroid polyhedra, An out-of-kilter method for the algebraic circulation problem, Finding feasible vectors of Edmonds-Giles polyhedra, An efficient algorithm for the bipartite matching problem, The maximum flow problem: A max-preflow approach, A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound, Invariant sets of arcs in network flow problems, Maximizing profits of routing in WDM networks, An improvement of Dijkstra's method for finding a shortest path in a graph, New solutions for disjoint paths in P systems, Computational experience with a polynomial-time dual simplex algorithm for the transportation problem, Balancing problems in acyclic networks, Improved filtering for the bin-packing with cardinality constraint, Two-edge connected spanning subgraphs and polyhedra, Fast approximate probabilistically checkable proofs, A generalization of the scaling max-flow algorithm, On the \(k\)-coloring of intervals, Using geometry to solve the transportation problem in the plane, Analysis of linear structured systems using a primal-dual algorithm, The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach, Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations, A capacity scaling algorithm for convex cost submodular flows, On perfectly two-edge connected graphs, An auction algorithm for the max-flow problem, Multimodal transport network systems interface, interaction coordination: A specification for control systems integration, Solving MIPs via scaling-based augmentation, A new strongly polynomial dual network simplex algorithm, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, Multiflows and disjoint paths of minimum total cost, Primal-dual target-following algorithms for linear programming, A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks, Minimum cut problem using bases of extended polymatroids, Optimal scheduling in CDMA packet radio networks, Planning of high school examinations in Denmark, Scheduling for electricity cost in a smart grid, A new algorithm to find the shortest paths between all pairs of nodes, Optimal cocircuits in regular matroids and applications, Complexity of linear programming, Convexification of generalized network flow problem, Formalizing network flow algorithms: a refinement approach in Isabelle/HOL, The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points., Unit disk graphs, A new scaling algorithm for the minimum cost network flow problem, The MA-ordering max-flow algorithm is not strongly polynomial for directed networks, On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem, Natalie 2.0: sparse global network alignment as a special case of quadratic assignment, Finding minimum-cost flows by double scaling, Refinement to imperative HOL, Tiers for peers: a practical algorithm for discovering hierarchy in weighted networks, Shortest augmenting paths for online matchings on trees, Critical objective function values in linear sum assignment problems, On the computational behavior of a polynomial-time network flow algorithm, Negative circuits for flows and submodular flows, Implementing the Ford-Fulkerson labeling algorithm with fixed-order scanning, Solving the optimum communication spanning tree problem, Coflow polyhedra, A new Karzanov-type \(O(n^ 3)\) max-flow algorithm, Greedy oriented flows, Time-dependent optimization of a multi-item uncertain supply chain network: a hybrid approximation algorithm, On graphs of the cone decompositions for the min-cut and max-cut problems, Distribution and reliability evaluation of MAX-flow in dynamic multi-state flow networks, Matching theory -- a sampler: From Dénes König to the present, The importance of memory for price discovery in decentralized markets, Colocating tasks in data centers using a side-effects performance model, The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases, Matching supply and demand in a sharing economy: classification, computational complexity, and application, Maximum \(k\)-covering of weighted transitive graphs with applications, Optimal multiple interval assignments in frequency assignment and traffic phasing, Chromatic number via Turán number, Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs, On survivable network polyhedra, A capacity scaling algorithm for M-convex submodular flow, A procedure to determine optimal partitions of weighted hypergraphs through a network-flow analogy, An improved upper bound on the expected regret of UCB-type policies for a matching-selection bandit problem, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, Maximum matchings of a digraph based on the largest geometric multiplicity, Numerical investigations on the maximal flow algorithm of Karzanov, Resilient capacity-aware routing, An analogue of Hoffman's circulation conditions for max-balanced flows, A comparison of two algorithms for the assignment problem, Testing the necklace condition for shortest tours and optimal factors in the plane, A maximum flow algorithm using MA ordering., An efficient algorithm for minimum-weight bibranching, Computational investigations of maximum flow algorithms, Routing trains through railway stations: Complexity issues, An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment, A bidirectional shortest-path algorithm with good average-case behavior, Parallel algorithm to find maximum capacity paths, Computing in combinatorial optimization, The minimum mean cycle-canceling algorithm for linear programs, Distribution-free and model-free multivariate feature screening via multivariate rank distance correlation, The continuous maximum capacity path interdiction problem, Robust drone selective routing in humanitarian transportation network assessment, Constructing a course schedule by solving a series of assignment type problems, Colored cut games, Test sets of integer programs, An algorithmic study of the maximum flow problem: A comparative statistical analysis, A note on practical construction of maximum bandwidth paths., A mechanized proof of the max-flow min-cut theorem for countable networks with applications to probability theory, Lexicographic optimal homologous chains and applications to point cloud triangulations, On the maximum capacity augmentation algorithm for the maximum flow problem, Tight bounds on the number of minimum-mean cycle cancellations and related results, A new saling algorithm for the maximum mean cut problem, Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs, Algorithms and complexity analysis for some flow problems, Parallel algorithms for the assignment and minimum-cost flow problems, The auction algorithm: A distributed relaxation method for the assignment problem, Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions, Reliability evaluation in terms of flow data mining for multistate networks, Network flow methods for the minimum covariate imbalance problem, Two deadline reduction algorithms for scheduling dependent tasks on parallel processors, Efficient dual simplex algorithms for the assignment problem, Spoke contour conversion for coverage diagrams, Recognizing graph search trees, OPTIMIZING DATA THROUGHPUT IN CLIENT/SERVER SYSTEMS BY KEEPING QUEUE SIZES BALANCED, Synthesis of directed multicommodity flow networks, Efficient many-to-Many point matching in one dimension, Interdistrict school choice: a theory of student assignment, TRAWLING TRAFFIC UNDER ATTACK OVERCOMING DDoS ATTACKS BY TARGET-CONTROLLED TRAFFIC FILTERING, Quadratically Regularized Optimal Transport on Graphs, Approximate solutions of capacitated fixed-charge minimum cost network flow problems, On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond, Smoothed Analysis of the Successive Shortest Path Algorithm, Community Detection in Temporal Multilayer Networks, with an Application to Correlation Networks, Design of microvascular flow networks using multi-objective genetic algorithms, Separation, dimension, and facet algorithms for node flow polyhedra, Affirmative action algorithms, On packing and coloring hyperedges in a cycle, A graph-oriented approach to address generically flat outputs in structured LTI discrete-time systems, Scaling: A general framework, A competitive (dual) simplex method for the assignment problem, A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm, Linear-Time Approximation for Maximum Weight Matching, Vertex deletion into bipartite permutation graphs, Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm, Classes of linear programs solvable by coordinate-wise minimization, Computing the sequence of \(k\)-cardinality assignments, Extending de Bruijn sequences to larger alphabets, Matching and scheduling of student-company-talks for a university it-speed dating event, Editing to a connected graph of given degrees, Computing the largest bond and the maximum connected cut of a graph, Network encoding complexity: exact values, bounds, and inequalities, A faster strongly polynomial time algorithm to solve the minimum cost tension problem, Minimum-cost flow algorithms: an experimental evaluation, Simple undirected two-commodity integral flow with a unitary demand, A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs, Finding optimal non-datapath caching strategies via network flow, An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem, Just-in-Time Scheduling with Equal-Size Jobs, Pareto stability in two-sided many-to-many matching with weak preferences, Topological learning for brain networks, Alternating signed bipartite graphs and difference-1 colourings, SS/TDMA Satellite Communications withk-Permutation Switching Modes, Mathematical estimation for maximum flow of goods within a cross-dock to reduce inventory, Coordinated cutting plane generation via multi-objective separation, (Arc-)disjoint flows in networks, On the fast delivery problem with one or two packages, Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier, Multi-project scheduling problem under shared multi-skill resource constraints, A Strongly Polynomial Algorithm for Generalized Flow Maximization, Enumerating \(k\)-arc-connected orientations, Packing and covering with integral feasible flows in integral supply-demand networks, Bike sharing systems: solving the static rebalancing problem, A sequential algorithm for finding a maximum weightK-independent set on interval graphs, On the edge capacitated Steiner tree problem, Topologically trivial closed walks in directed surface graphs, Second-price ad auctions with binary bids and markets with good competition, Quantitative Models for Infrastructure Restoration After Extreme Events: Network Optimization Meets Scheduling, Optimal transport: discretization and algorithms, A NEW APPROACH FOR SOLVING THE MINIMUM COST FLOW PROBLEM WITH INTERVAL AND FUZZY DATA, Rényi 100, quantitative and qualitative (in)dependence, Near Approximation of Maximum Weight Matching through Efficient Weight Reduction, Algorithms for flows with parametric capacities, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Efficient preflow push algorithms, A primal simplex variant for the maximum-flow problem, Algorithms for topology-free and alignment network queries, Complexity and algorithms for nonlinear optimization problems, Integer programming models for the multidimensional assignment problem with star costs, Iterative compression and exact algorithms, A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm, Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design, Iterative Compression and Exact Algorithms, Shortest Augmenting Paths for Online Matchings on Trees, On the complexity of resilient network design, Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem, Balanced-flow algorithm for path network planning in hierarchical spaces, Faster Algorithms for Semi-Matching Problems, Optimizing compatible sets in wireless networks through integer programming, An algorithm for then×n optimum assignment problem, Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, Formalizing the Edmonds-Karp Algorithm, Disjoint Spread Systems and Fault Location, A new algorithm for the assignment problem, Distributed Evacuation in Graphs with Multiple Exits, Decomposition algorithms for minimal cut problems, Stability of the Bipartite Matching Model, Maximum-throughput dynamic network flows, Decomposition algorithms for locating minimal cuts in a network, The traveling salesman problem: An update of research, The \(\alpha\)-maximum flow model with uncertain capacities, On chromatic number and minimum cut, Automatic Graph-Based Local Edge Detection, Probabilistic \(k\)-median clustering in data streams, Critical extreme points of the 2-edge connected spanning subgraph polytope, Scheduling for Electricity Cost in Smart Grid, Decentralized maximum-flow protocols, A fast parallel algorithm for minimum-cost small integral flows, Short simplex paths in lattice polytopes, Determining minimal cuts with a minimal number of arcs
