Open AccessExact and Heuristic Algorithms for Multi-constrained Path Selection Problem
Author(s) -
Wen-Lin Yang
Publication year - 2002
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/3-540-36228-2_118
Subject(s) - computer science , tabu search , heuristic , mathematical optimization , path (computing) , selection (genetic algorithm) , set (abstract data type) , network topology , algorithm , point (geometry) , quality of service , mathematics , artificial intelligence , computer network , geometry , programming language
The multi-constrained path (MCP) selection problem occurs when the quality of services (QoS) are supported for point-to-point connections in the distributed multimedia applications deployed on the Internet. This NP-complete problem is concerned how to determine a feasible path between two end-points, so that a set of QoS path constraints can be satisfied simultaneously. Based on the branch-and-bound technology and tabu-searching strategy, an optimal algorithm and a heuristic algorithm are proposed in this paper. The experimental results show that our heuristic algorithm not only has very good performance on several different network topologies, but also is very efficient method for solving large-scale MCP problem.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom