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/).

Download article (PDF)

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  -