Title :
Formal Programming for the Shortest Path and Its Critical Edge Problems
Author :
Zheng, Yujun ; Xue, Jinyun ; Shi, Haihe
Abstract :
Many problems in operations research can be formulated in terms of networks, among which the shortest path is a particularly important class. Using the PAR method, we formally derive and implement algorithmic programs for three typical network problems, including the shortest path tree (SPT) problem, the most vital edge (MVE) problem, and the real time critical edge (RTCE) problem, which are motivated by routing applications. The main ideas and ingenuity of these algorithms are revealed by formula deduction.
Keywords :
trees (mathematics); ubiquitous computing; critical edge problems; formal programming; most vital edge problem; operations research; real time critical edge problem; routing applications; shortest path tree problem; Algorithm design and analysis; Automatic programming; Design automation; Design methodology; Dynamic programming; High performance computing; Laboratories; Logistics; Operations research; Partitioning algorithms; Algorithmic programs; Critical edge; Networks; PAR method; Shortest path;
Conference_Titel :
Automation and Logistics, 2007 IEEE International Conference on
Conference_Location :
Jinan
Print_ISBN :
978-1-4244-1531-1
DOI :
10.1109/ICAL.2007.4338533
