Labeled shortest paths in digraphs with negative and positive edge weights
Phillip G. Bradford; David A. Thomas
RAIRO - Theoretical Informatics and Applications (2009)
- Volume: 43, Issue: 3, page 567-583
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topReferences
top- C. Barrett, R. Jacob and M. Marathe, Formal-language-constrained path problems. SIAM J. Comput.30 (2000) 809–837.
- C. Barrett, K. Bisset, M. Holzer, G. Konjevod, M. Marathe and D. Wagner, Label Constrained Shortest Path Algorithms: An Experimental Evaluation using Transportation Networks. Tech. Report: Virginia Tech (USA), Arizona State University (USA), and Karlsruhe University (Germany), Presented at at the workshop on the DIMACS Shortest-Path Challenge, http://i11www.ira.uka.de/algo/people/mholzer/publications/pdf/bbhkmw-lcspa-07.pdf
- C. Barrett, K. Bisset, R. Jacob, G. Konejevod and M. Marathe, Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSMIS router. European Symposium on Algorithms (ESA 02). Lect. Notes Comput. Sci.2461 (2002) 126–138.
- P.G. Bradford and V. Choppella, Fast Dyck and semi-Dyck constrained shortest paths on DAGs (submitted).
- D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput.9 (1990) 251–280.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd edition. MIT Press (2001).
- R. Greenlaw, H.J. Hoover and W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory. Oxford University Press (1995).
- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979).
- D.B. Johnson, Efficient algorithms for shortest paths in sparse networks. J. ACM24(1) (1977) 1–13.
- A.O. Mendelzon and P.T. Wood, Finding regular simple paths in graph databases. SIAM J. Comput.24 (1995) 1235–1258.
- M. Nykänen and E. Ukkonen, The exact path length problem. J. Algor.42 (2002) 41–53.
- W.L. Ruzzo, Complete pushdown languages. Unpublished manuscript (1979).
- M. Yannakakis, Graph-theoretic methods in database theory. In Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS '90). ACM, New York, NY (1990) 230–242.
- U. Zwick, Exact and Approximate Distances in Graphs – A survey. In Proceedings of the Ninth ESA (2001) 33–48.