Length 3 Edge-Disjoint Paths Is NP-Hard.
Hannah AlpertJennifer IglesiasPublished in: Comput. Complex. (2012)
Keyphrases
- disjoint paths
- approximation algorithms
- np hard
- special case
- undirected graph
- set cover
- np hardness
- minimum cost
- scheduling problem
- linear programming
- integer programming
- np complete
- worst case
- constraint satisfaction problems
- decision problems
- optimal solution
- directed graph
- computational complexity
- approximation ratio
- branch and bound algorithm
- lower bound
- search algorithm
- greedy heuristic
- closely related
- remains np hard