DocumentCode
3468172
Title
Formal Programming for the Shortest Path and Its Critical Edge Problems
Author
Zheng, Yujun ; Xue, Jinyun ; Shi, Haihe
fYear
2007
fDate
18-21 Aug. 2007
Firstpage
72
Lastpage
76
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Automation and Logistics, 2007 IEEE International Conference on
Conference_Location
Jinan
Print_ISBN
978-1-4244-1531-1
Type
conf
DOI
10.1109/ICAL.2007.4338533
Filename
4338533
Link To Document