Scaling algorithms for network problems

DOI10.1016/0022-0000(85)90039-XzbMath0596.90095OpenAlexW2139559590WikidataQ56078240 ScholiaQ56078240MaRDI QIDQ1079135

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90039-x

zbMATH Keywords

scaling minimum cost flow minimum spanning tree network problems bottleneck shortest path degree- constrained subgraph maximum network flow weight matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory to circuits and networks (94C15)

Related Items

Optimum matchings in weighted bipartite graphs, A generalization of the scaling max-flow algorithm, A fast cost scaling algorithm for submodular flow, Recent developments in maximum flow algorithms, River routing in VLSI, On the exponent of all pairs shortest path problem, Linear-Time Approximation for Maximum Weight Matching, Weighted approximate parameterized string matching, A faster strongly polynomial time algorithm to solve the minimum cost tension problem, 0/1-Integer programming: Optimization and Augmentation are equivalent, An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem, Minimum-cost flows in unit-capacity networks, A Filtering Technique for All Pairs Approximate Parameterized String Matching, The symbolic algorithms for maximum flow in networks, A parallel algorithm for eliminating cycles in undirected graphs, An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem, Generating pseudo-random permutations and maximum flow algorithms, A simple reduction from maximum weight matching to maximum cardinality matching, An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem, A new scaling algorithm for the minimum cost network flow problem, Bi-criteria and approximation algorithms for restricted matchings, On graphs preserving rectilinear shortest paths in the presence of obstacles, Finding minimum-cost flows by double scaling, Critical objective function values in linear sum assignment problems, On the computational behavior of a polynomial-time network flow algorithm, A scaling technique for finding the weighted analytic center of a polytope, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, Minimax inverse problems of minimum cuts, AO(nm log(U/n)) time maximum flow algorithm, Single source shortest paths in \(H\)-minor free graphs, Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem, A feasibility evaluation approach for time-evolving multi-item production–distribution networks, Computational investigations of maximum flow algorithms, Maximum weight bipartite matching in matrix multiplication time, Test sets of integer programs, Lexicographic bottleneck combinatorial problems, A linear time algorithm for the maximum capacity path problem, Parallel algorithms for the assignment and minimum-cost flow problems, The maximum flow problem: A max-preflow approach, Short simplex paths in lattice polytopes

Uses Software

Algorithm 360

Cites Work