Title :
An Algorithm for Dynamic Optimal Path Selection with Constraint
Author :
Qi, Xiaogang ; Liu, Lifang ; Liu, Sanyang
Author_Institution :
Dept. of Appl. Math., Xidian Univ., Xi´´an
Abstract :
Optimal path selection (OPS) with unique or multiple constraints is one of key issues in the dynamic networks, in which arc´ weight metric is an interval number. Firstly, some existing solutions for this problem are analyzed, and some shortages and flaws are pointed out. Secondly, regularities of distribution of the summation of multiple independent random numbers with same and different distributions are analyzed and formulated by data simulating and fitting. Furthermore, an algorithm named DOPS_Const for the OPS with an additive arc weight is proposed based on the above analysis, and the randomness and subjectivity in path selection can be avoided according to the algorithm. Finally, the theoretical and statistical probabilities of the selected path satisfying the given constraint are compared, and our algorithm is feasible and valid to solve the OPS with constraint in the dynamic networks.
Keywords :
graph theory; number theory; random processes; arc weight metric; dynamic network; dynamic optimal path selection; graph theory; interval number; multiple constraint; multiple independent random number; Algorithm design and analysis; Analytical models; Computer networks; Computer science; Constraint theory; Fitting; Graph theory; Heuristic algorithms; Mathematics; Probability; additive weight; constrained path selection; distribution of the summation of parameters; dynamic networks; network algorithm design;
Conference_Titel :
Young Computer Scientists, 2008. ICYCS 2008. The 9th International Conference for
Conference_Location :
Hunan
Print_ISBN :
978-0-7695-3398-8
Electronic_ISBN :
978-0-7695-3398-8
DOI :
10.1109/ICYCS.2008.21
