Almost Polynomial Hardness of Node-Disjoint Paths in Grids.

Julia Chuzhoy David H. K. Kim Rachit Nimavat

Published in: CoRR (2017)

Keyphrases

disjoint paths
directed graph
approximation algorithms
undirected graph
np hard
worst case
agnostic learning
information theoretic
image processing
learning theory
np hardness
computational complexity
constraint satisfaction problems
connected components
random walk
np complete
multi dimensional
dynamic programming