Lower Bounds for On-line Graph Problems with Application to On-line Circuit and Optical Routing.

Yair Bartal Amos Fiat Stefano Leonardi

Published in: SIAM J. Comput. (2006)

Keyphrases

lower bound
upper bound
np complete
randomly generated problems
social networks
shortest path
graph model
data structure
wireless sensor networks
scheduling problem
high speed
optimization problems
random walk
bipartite graph
graph structure
min sum