Dynamic Data Structures for Series Parallel Digraphs

Giuseppe F. Italiano; Alberto Marchetti Spaccamela; Umberto Nanni

Dynamic Data Structures for Series Parallel Digraphs
Italiano, Giuseppe F.
Spaccamela, Alberto Marchetti
Nanni, Umberto
Computer Science
Persistent URL:
Columbia University Computer Science Technical Reports
Part Number:
Department of Computer Science, Columbia University
Publisher Location:
New York
We consider the problem of dynamically maintaining general series parallel directed acyclic graphs (GSP dags), two-terminal series parallel directed acyclic graphs (TTSP dags) and looped series parallel directed graphs (looped SP digraphs). We present data structures for updating (by both inserting and deleting either a group of edges or vertices) GSP dags, TTSP clags and looped SP digraphs of m edges and n vertices in O( log n) worst-case time. The time required to check whether there is a path between two given vertices is O(log n), while a path of length k can be traced out in O(k + log n) time. For GSP and TTSP dags, our data structures are able to report a regular expression describing all the paths between two vertices x and y in O(h + log n), where h ≤ n is the total number of vertices which are contained in paths from x to y. Although GSP dags can have as many as O(n2) edges, we use an implicit representation which requires only O(n) space. Motivations for studying dynamic graphs arise in several areas, such as communication networks, Incremental compilation environments and the design of very high level languages, while the dynamic maintenance of series parallel graphs is also relevant in reducible flow diagrams.
Computer science
Item views
text | xml
Suggested Citation:
Giuseppe F. Italiano, Alberto Marchetti Spaccamela, Umberto Nanni, , Dynamic Data Structures for Series Parallel Digraphs, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ