A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.
Jin-Yi CaiXi ChenPublished in: Comput. Complex. (2019)
Keyphrases
- directed graph
- random walk
- edge weights
- positive and negative
- graph structure
- maximum flow
- strongly connected
- linear combination
- directed acyclic graph
- undirected graph
- disjoint paths
- shortest path problem
- graph theory
- first order logic
- sensor networks
- transitive closure
- random variables
- datalog programs
- special case
- search algorithm