Almost Polynomial Hardness of Node-Disjoint Paths in Grids.
Julia ChuzhoyDavid Hong Kyun KimRachit NimavatPublished in: Theory Comput. (2021)
Keyphrases
- disjoint paths
- approximation algorithms
- directed graph
- undirected graph
- np hard
- worst case
- np hardness
- phase transition
- computational complexity
- grid computing
- learning theory
- np complete
- information theoretic
- random walk
- minimum cost
- multi dimensional
- state space
- agnostic learning
- image processing
- irregular isothetic grids