Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874781 | Journal of Discrete Algorithms | 2016 | 11 Pages |
Abstract
The Graph Level Order Unary Degree Sequence (GLOUDS) is a new succinct data structure for directed graphs that are “tree-like,” in the sense that the number of “additional” edges (w.r.t. a spanning tree) is not too high. The algorithmic idea is to represent a BFS-spanning tree of the graph (consisting of n nodes) with a well known succinct data structure for trees, named LOUDS, and enhance it with additional information that accounts for the non-tree edges. In practical tests, our data structure performs well for graphs containing up to m=5n edges, while still having competitive running times for listing adjacent nodes.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Johannes Fischer, Daniel Peters,