Efficient and Effective Directed Minimum Spanning Tree Queries

Zhuoran Wang, Dian Ouyang (), Yikun Wang, Qi Liang and Zhuo Huang
Additional contact information
Zhuoran Wang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 511400, China
Dian Ouyang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 511400, China
Yikun Wang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 511400, China
Qi Liang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 511400, China
Zhuo Huang: Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 511400, China

Mathematics, 2023, vol. 11, issue 9, 1-17

Abstract: Computing directed Minimum Spanning Tree ( D M S T ) 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 D M S T 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 D M S T in a hierarchical tree in O ( n ) space complexity. Furthermore, we answer the D M S T 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.

Keywords: directed minimum spanning tree; indexed approach; batch query (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/9/2200/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/9/2200/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:9:p:2200-:d:1141029

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().