Minimum-cost augmentation to 3-edge-connect all specified vertices in a graph.
Toshimasa WatanabeSatoshi TaokaToshiya MashimaPublished in: ISCAS (1993)
Keyphrases
- minimum cost
- undirected graph
- spanning tree
- edge weights
- approximation algorithms
- weighted graph
- np hard
- adjacency matrix
- vertex set
- random graphs
- network flow
- capacity constraints
- network flow problem
- network simplex algorithm
- minimum weight
- strongly connected
- minimum cost flow
- connected components
- shortest path
- directed graph
- worst case
- special case