Dynamic Routing Schemes for General Graphs

摘要: This paper studies approximate distributed routing schemes on dynamic communication networks. The focuses weighted general graphs where the vertices of graph are fixed but weights edges may change. Our main contribution concerns bounding cost adapting to changes. update efficiency a scheme is measured by number messages that need be sent, following weight change, in order scheme. results indicate theoretic parameter governing amortized message complexity these updates local density D underlying graph, and specifically, this ${\tilde\Theta}(D)$. also establishes upper lower bounds size databases required at each site.