Scaling algorithms for network problems (Q1079135)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Scaling algorithms for network problems |
scientific article |
Statements
Scaling algorithms for network problems (English)
0 references
1985
0 references
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.
0 references
network problems
0 references
minimum spanning tree
0 references
bottleneck shortest path
0 references
maximum network flow
0 references
minimum cost flow
0 references
weight matching
0 references
degree- constrained subgraph
0 references
scaling
0 references