首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Shortest paths algorithms: Theory and experimental evaluation
Authors:Boris V Cherkassky  Andrew V Goldberg  Tomasz Radzik
Institution:(1) Central Institute for Economics and Mathematics, Krasikova St. 32, 117418 Moscow, Russia;(2) Computer Science Department, Stanford University, 94305 Stanford, CA, USA;(3) Department of Computer Science, King's College London, WC2R 2LS London, UK;(4) Present address: NEC Research Institute, 4 Independence Way, 08540 Princeton, NJ
Abstract:We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.
Keywords:Graph algorithms  Network optimization  Shortest paths  Theory and experimental evaluation of algorithms
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号