Approximation algorithms for minimum-cost k-vertex connected subgraphs.
Joseph CheriyanSantosh S. VempalaAdrian VettaPublished in: STOC (2002)
Keyphrases
- approximation algorithms
- minimum cost
- connected subgraphs
- np hard
- biological networks
- directed acyclic graph
- network flow
- special case
- connected components
- worst case
- spanning tree
- undirected graph
- network flow problem
- primal dual
- network design problem
- approximation ratio
- combinatorial auctions
- biological systems
- gene expression
- constant factor
- bayesian networks