GLOUDS: Representing tree-like graphs
GLOUDS: Representing tree-like graphs
复制标题
GLOUDS：表示树状图
DOI：
10.1016/j.jda.2015.10.004
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
D. Peters
中科院分区：
文献类型：
--
作者：
J. Fischer;D. Peters
图级序一元序列（GLOUDS）是一种新的简洁的数据结构，用于“树状”的有向图，因为“附加”边的数量（生成树的数量）不会太高。算法思想是用众所周知的树的简洁数据结构LOUDS来表示图的bfs生成树（由n个节点组成），并使用说明非树边的附加信息来增强它。在实际测试中，我们的数据结构在包含多达m= 5n条边的图中表现良好，同时在列出相邻节点时仍然具有竞争的运行时间。
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 (wrt 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= 5 n edges, while still having competitive running times for listing adjacent nodes.
登录
查看更多内容
集合的紧凑表示
DOI：
10.1007/978-3-642-25591-5_32
发表时间：
2011
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Arash Farzan;J. Fischer
通讯作者：
J. Fischer
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
R. Grossi;Ankur Gupta;J. Vitter
通讯作者：
R. Grossi;Ankur Gupta;J. Vitter
影响因子：
4
作者：
S. Joannou;R. Raman
通讯作者：
R. Raman
DOI：
10.1007/978-3-642-38527-8_3
发表时间：
2013
期刊：
J. ACM
影响因子：
--
作者：
R. Grossi;G. Ottaviano
通讯作者：
G. Ottaviano
DOI：
10.1007/978-3-540-69903-3_17
发表时间：
2008
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Arash Farzan;J. I. Munro
通讯作者：
J. I. Munro