×

Orienting fully dynamic graphs with worst-case time bounds. (English) Zbl 1411.68084

Esparza, Javier (ed.) et al., Automata, languages, and programming. 41st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014. Proceedings, Part II. Berlin: Springer. Lect. Notes Comput. Sci. 8573, 532-543 (2014).
Summary: In edge orientations, the goal is usually to orient (direct) the edges of an undirected network (modeled by a graph) such that all out-degrees 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.
G. S. Brodal and R. Fagerberg [Lect. Notes Comput. Sci. 1663, 342–351 (1999; Zbl 1063.68571)] 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 O. Neiman and S. Solomon [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC’13. New York, NY: Association for Computing Machinery (ACM). 745–754 (2013; Zbl 1293.05304)].
For the entire collection see [Zbl 1291.68018].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv