文献详情
Balanced-flow algorithm for path network planning in hierarchical spaces
文献类型：期刊
通讯作者：Hong, Y (reprint author), Beijing Forestry Univ, Sch Informat Sci & Technol, Beijing 100083, Peoples R China.
期刊名称：THEORETICAL COMPUTER SCIENCE影响因子和分区
年：2020
卷：803
页码：196-206
ISSN：0304-3975
关键词：Path planning; Hierarchical space; Balanced-flow path network; Batch scheduling
所属部门：信息学院
摘要：Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination ...More
Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. (C) 2019 Elsevier B.V. All rights reserved. ...Hide

DOI：10.1016/j.tcs.2019.10.028
百度学术：Balanced-flow algorithm for path network planning in hierarchical spaces
语言：外文
基金：National Natural Science Foundation of ChinaNational Natural Science Foundation of China [11671400]; General Project of Science and Technology Plan of Beijing Municipal Education Commission [KM201910017006]; Program of Beijing Excellent Talents Training for Young Scholar [2016000020124G056]
作者其他论文



A New Greedy Algorithm for Constructing the Minimum Size Connected Dominating Sets in Wireless Networks.Luo, Chuanwen, Wang, Yongcai, Yu, Jiguo, et al. .WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, WASA 2017. 2017, 10251, 109-114.
Fair Multi-influence Maximization in Competitive Social Networks.Yu, Ying, Jia, Jinglan, Li, Deying, et al. .WIRELESS ALGORITHMS, SYSTEMS, AND APPLICATIONS, WASA 2017. 2017, 10251, 253-265.
WCS: Weighted Component Stitching for Sparse Network Localization.Sun, Tianyuan, Wang, Yongcai, Li, Deying, et al. .IEEE-ACM TRANSACTIONS ON NETWORKING. 2018, 26(5), 2242-2253.
Robust Component-based Network Localization with Noisy Range Measurements.Sun, Tianyuan, Wang, Yongcai, Li, Deying, et al. .2018 27TH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATION AND NETWORKS (ICCCN). 2018.
Robust Passive Location in Zero-Calibrated Environment Using Smoothed Ordinal Constraints.Ye, Xuehan, Lei, Zhixian, Wang, Yongcai, et al. .2017 14TH INTERNATIONAL SYMPOSIUM ON PERVASIVE SYSTEMS, ALGORITHMS AND NETWORKS & 2017 11TH INTERNATIONAL CONFERENCE ON FRONTIER OF COMPUTER SCIENCE AND TECHNOLOGY & 2017 THIRD INTERNATIONAL SYMPOSIUM OF CREATIVE COMPUTING (ISPAN-FCST-ISCC). 2017