Scaling algorithms for network problems
bottleneck shortest pathdegree- constrained subgraphmaximum network flowminimum cost flowminimum spanning treenetwork problemsscalingweight matching
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35) Applications of graph theory to circuits and networks (94C15)
The network problems as, e.g., minimum spanning tree, bottleneck shortest path, shortest path with nonnegative lengths and shortest path with arbitrary lengths, maximum network flow, minimum cost flow in a network with unit capacities, maximum weight matching in bipartite graphs and degree-constrained subgraph can be solved by scaling the numeric parameters of a given edge-weighted graph. An algorithm for scaling is proposed such that its application gives a method being superior to the traditional ones. The numerical complexities of the best known traditional algorithms are compared with those derived here for scaling algorithms.
- Faster Scaling Algorithms for Network Problems
- Computing optimal scalings by parametric network algorithms
- The Scaling Network Simplex Algorithm
- Scaling: a canonical design problem for networks
- scientific article; zbMATH DE number 1003254
- Scalable Algorithms for Data and Network Analysis
- Scaling Algorithms for the Shortest Paths Problem
- scientific article; zbMATH DE number 437547
- scientific article; zbMATH DE number 3900472
- scientific article; zbMATH DE number 1875405
- A data structure for dynamic trees
- A good algorithm for smallest spanning trees with a degree constraint
- A note on two problems in connexion with graphs
- A Shortest Path Algorithm for Edge-Sparse Graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 3475221 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 3231693 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- Network Flow and Testing Graph Connectivity
- On a routing problem
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Maximum weight bipartite matching in matrix multiplication time
- River routing in VLSI
- On graphs preserving rectilinear shortest paths in the presence of obstacles
- Finding minimum-cost flows by double scaling
- On the computational behavior of a polynomial-time network flow algorithm
- Computational investigations of maximum flow algorithms
- Test sets of integer programs
- Lexicographic bottleneck combinatorial problems
- Parallel algorithms for the assignment and minimum-cost flow problems
- On the exponent of all pairs shortest path problem
- Minimum-cost flows in unit-capacity networks
- Critical objective function values in linear sum assignment problems
- A generalization of the scaling max-flow algorithm
- A new scaling algorithm for the minimum cost network flow problem
- Short simplex paths in lattice polytopes
- Weighted approximate parameterized string matching
- A faster strongly polynomial time algorithm to solve the minimum cost tension problem
- An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem
- The symbolic algorithms for maximum flow in networks
- Bi-criteria and approximation algorithms for restricted matchings
- Optimum matchings in weighted bipartite graphs
- Minimax inverse problems of minimum cuts
- 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
- A fast cost scaling algorithm for submodular flow
- scientific article; zbMATH DE number 437547 (Why is no real title available?)
- Linear-time approximation for maximum weight matching
- An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem
- scientific article; zbMATH DE number 1472098 (Why is no real title available?)
- AO(nm log(U/n)) time maximum flow algorithm
- A simple reduction from maximum weight matching to maximum cardinality matching
- An affine scaling method for solving network flow problems
- Faster Scaling Algorithms for Network Problems
- Scaling Algorithms for the Shortest Paths Problem
- Recent developments in maximum flow algorithms
- A filtering technique for all pairs approximate parameterized string matching
- Scaling: a canonical design problem for networks
- Scalable Algorithms for Data and Network Analysis
- 0/1-Integer programming: Optimization and Augmentation are equivalent
- An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem
- A scaling technique for finding the weighted analytic center of a polytope
- Two strongly polynomial cut cancelling algorithms for minimum cost network flow
- Negative-weight single-source shortest paths in near-linear time
- Maximum flow and minimum-cost flow in almost-linear time
- Approximate min-sum subset convolution
- Fully dynamic algorithms for minimum weight cycle and related problems
- Quantum speedups for polynomial-time dynamic programming algorithms
- A linear time algorithm for the maximum capacity path problem
- The maximum flow problem: A max-preflow approach
- A parallel algorithm for eliminating cycles in undirected graphs
- Generating pseudo-random permutations and maximum flow algorithms
- Single source shortest paths in H-minor free graphs
This page was built for publication: Scaling algorithms for network problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079135)
