Graph decomposition and a greedy algorithm for edge-disjoint paths.
Kasturi R. VaradarajanGanesh VenkataramanPublished in: SODA (2004)
Keyphrases
- disjoint paths
- greedy algorithm
- directed graph
- approximation algorithms
- undirected graph
- worst case
- greedy algorithms
- set cover
- objective function
- dynamic programming
- greedy heuristic
- influence maximization
- greedy strategy
- greedy approximation algorithm
- influence spread
- approximation guarantees
- graph structure
- knapsack problem
- directed acyclic graph
- weighted graph
- submodular functions
- random walk
- website