期刊
MATHEMATICS
卷 11, 期 9, 页码 -出版社
MDPI
DOI: 10.3390/math11092200
关键词
directed minimum spanning tree; indexed approach; batch query
类别
Computing directed Minimum Spanning Tree (DMST) is a fundamental problem in graph theory, applied in various fields such as computer network, communication protocol design, revenue maximization in social networks, and syntactic parsing in Natural Language Processing. This paper proposes an indexed approach that reuses computation results for single and batch queries of DMST, achieving significant speedup while consuming minimal index size.
Computing directed Minimum Spanning Tree (DMST) is a fundamental problem in graph theory. It is applied in a wide spectrum of fields from computer network and communication protocol design to revenue maximization in social networks and syntactic parsing in Natural Language Processing. State-of-the-art solutions are online algorithms that compute DMST for a given graph and a root. For multi-query requirements, the online algorithm is inefficient. To overcome the drawbacks, in this paper, we propose an indexed approach that reuses the computation result to facilitate single and batch queries. We store all the potential edges of DMST in a hierarchical tree in O(n) space complexity. Furthermore, we answer the DMST query of any root in O(n) time complexity. Experimental results demonstrate that our approach can achieve a speedup of 2-3 orders of magnitude in query processing compared to the state-of-the-art while consuming O(n) index size.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据