Lower Bounds for Graph Exploration Using Local Policies.
Aditya Kumar AkashSándor P. FeketeSeoung Kyou LeeAlejandro López-OrtizDaniela MaftuleacJames McLurkinPublished in: WALCOM (2016)
Keyphrases
- lower bound
- upper bound
- min sum
- weighted graph
- graph theory
- branch and bound
- np hard
- directed acyclic graph
- objective function
- random walk
- graph theoretic
- structured data
- graph representation
- graph structure
- optimal solution
- lower and upper bounds
- branch and bound algorithm
- directed graph
- optimal policy
- bipartite graph
- spanning tree
- vc dimension
- shortest path
- upper and lower bounds
- linear programming relaxation
- worst case