IJPAM: Volume 2, No. 3 (2002)
ON A CLASS OF SHORTEST PATH
ALGORITHMS WITH DISRUPTIVE SEARCH GRAPHS
ALGORITHMS WITH DISRUPTIVE SEARCH GRAPHS
Ming-Jer Tsai
Computer and Communications Research Laboratories
Industrial Technology Research Institute
R.M. 470, BLDG 51, No. 195, Sec. 4
Chung-Hsing R.D. Chutung
Hsinchu, Taiwan, ROC
e-mail: [email protected]
Computer and Communications Research Laboratories
Industrial Technology Research Institute
R.M. 470, BLDG 51, No. 195, Sec. 4
Chung-Hsing R.D. Chutung
Hsinchu, Taiwan, ROC
e-mail: [email protected]
Abstract.A shortest path algorithm constructs the search graph when it searches a
network. A disruptive search graph remains disconnected once it disconnects.
In this paper, a class of shortest path algorithms that construct disruptive
search graphs is found. By its aid, an arbitrary compromise between the time
delay and the checking frequency for negative-cycle detection can be made.
Received: April 8, 2002
AMS Subject Classification: 05C85, 68Q20, 68R10
Key Words and Phrases: negative-cycle detection, search graph, shortest path algorithm
Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2002
Volume: 2
Issue: 3
