Competitive Decision Algorithm for the Rooted Delay-constrained Minimum Spanning Tree
- DOI
- 10.2991/icaise.2013.19How to use a DOI?
- Keywords
- Competitive decision algorithm, Spanning tree;rooted delay--constrained minimum spanning tree, Competitiveness function, Decision function
- Abstract
In this paper, we make research on rooted delay-constrained minimum spanning tree (RDCMST). RDCMST seeks to find a minimum spanning tree and no path from a specified root node to any other nodes may exceed a given delay bound. RDCMST is a NP-hard combinatorial optimization problem which arises both in scientific research and practical engineering. Competitive decision algorithm (CDA) is a newly proposed meta-heuristic algorithm for solving complex combinatorial optimization problems. According to the general model of CDA, a CDA for RDCMST problem is proposed. RCL and randomly choosing resource are first introduced in CDA. And the search space is reduced after researching on the mathematical properties of RDCMST. And numerical computational experiments are performed to evaluate the algorithm.
- Copyright
- © 2013, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Xiaohua Xiong AU - Xuemin Chen AU - Aibing Ning PY - 2013/08 DA - 2013/08 TI - Competitive Decision Algorithm for the Rooted Delay-constrained Minimum Spanning Tree BT - Proceedings of the 2013 The International Conference on Artificial Intelligence and Software Engineering (ICAISE 2013) PB - Atlantis Press SP - 82 EP - 86 SN - 1951-6851 UR - https://doi.org/10.2991/icaise.2013.19 DO - 10.2991/icaise.2013.19 ID - Xiong2013/08 ER -