Frank Dehne, Jörg-Rüdiger Sack, Arvind Gupta, Roberto Tamassia
1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 unknown4 Department of Computer Science, Science and Technology, Aarhus University
We present a linear space data structure for maintaining graphs with bounded arboricity—a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth—under edge insertions, edge deletions, and adjacency queries. The data structure supports adjacency queries in worst case O(c) time, and edge insertions and edge deletions in amortized O(1) and O(c+log n) time, respectively, where n is the number of nodes in the graph, and c is the bound on the arboricity.
Lecture Notes in Computer Science: 6th International Workshop, Wads’99 Vancouver, Canada, August 11–14, 1999 Proceedings, 1999, p. 773-782
Main Research Area:
Lecture Notes in Computer Science
6th International Workshop on Algorithms and Data Structures. WADS 1999