A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph.
Michal DoryMohsen GhaffariPublished in: CoRR (2022)
Keyphrases
- minimum cost
- approximation algorithms
- np hard
- undirected graph
- approximation ratio
- network flow
- spanning tree
- capacity constraints
- minimum cost flow
- network flow problem
- network simplex algorithm
- worst case
- special case
- edge detection
- optimal solution
- connected components
- scheduling problem
- minimum cost path
- graph mining
- integer programming
- dynamic programming
- constant factor