Orienting Fully Dynamic Graphs with Worst-Case Time Bounds

摘要

In edge orientations, the goal is usually to orient (direct) the edges of an undirected network (modeled by a graph) such that all outdegrees are bounded. When the network is fully dynamic, i.e., admits edge insertions and deletions, we wish to maintain such an orientation while keeping a tab on the update time. Low out-degree orientations turned out to be a surprisingly useful tool for managing networks. Brodal and Fagerberg (1999) initiated the study of the edge orientation problem in terms of the graph's arboricity, which is very natural in this context. Their solution achieves a constant out-degree and a logarithmic amortized update time for all graphs with constant arboricity, which include all planar and excluded-minor graphs. It remained an open question - first proposed by Brodal and Fagerberg, later by Erickson and others - to obtain similar bounds with worst-case update time. We address this 15 year old question by providing a simple algorithm with worst-case bounds that nearly match the previous amortized bounds. Our algorithm is based on a new approach of maintaining a combinatorial invariant, and achieves a logarithmic out-degree with logarithmic worst-case update times. This result has applications to various dynamic network problems such as maintaining a maximal matching, where we obtain logarithmic worst-case update time compared to a similar amortized update time of Neiman and Solomon (2013).