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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references