- 1 AHO, A.V, and Ullman, J D The Theory of parsing Translation and computing, Volume II Compthng Prentice-Hall, Englewood Cliffs, N J, 1972, p 915 Google Scholar
- 2 AHO, A V AND ULLMAN, J D Principles of Compder Design Addison-Wesley, Reading, Mass, 1977, pp 408-517 Google Scholar
- 3 ALLEN, F E Control flow analysis SIGPLAN Nonces 5, 7 (1970), 1-19 Google Scholar
- 4 BACKHOUSE, R C AND CARRI5., B A Regular algebra apphed to path-finding problems J Inst Math Apphc, 15 (1975), 161-186Google Scholar
- 5 BUNCH, J R, AND ROSE, D J PartmonIng, tearing, and modification of sparse hnear systems J Math Anal Apphc 48 (1974), 574-593Google Scholar
- 6 CARRIe, B A An algebra for network routing problems J lnst Math Apphc 7 (1971), 273-294Google Scholar
- 7 DIJKSTRA, W A Dlwtphne of Programmmg Prentice-Hall, Englewood Cliffs, N J, 1976Google Scholar
- 8 DUFF, I S A survey of sparse matrix research Proc IEEE 65 (1977), 500-535Google Scholar
- 9 FARROW, R Efficient variants of path compression on unbalanced trees Unpublished manuscript, 1978Google Scholar
- 10 FLOYD, R Algorithm 97 Shortest path Commun A CM 5, 6 (June 1962), 345 Google Scholar
- 11 FORS~THE, G E, AND MOLER, C B Computer Solution of Linear Algebraic Equations Prentice-Hall, Englewood Chffs, N J, 1967Google Scholar
- 12 GRAHAM, S L, AND WEGMAN, M A fast and usually linear algorithm for global flow analysis J ACM 23, 1 (Jan 1976), 172-202 Google Scholar
- 13 HECHT, M.S Flow Analysts of Computer Programs Elsevter, New York, 1977 Google Scholar
- 14 HECHT, M.S, AND ULLMAN, J.D Flow graph reducibility SIAM J Comput. 1 (1972), 188-202Google Scholar
- 15 HECHT, M S AND ULLMAN, J D Characterizations of reducible flow graphs J A CM 21, 3 (July 1974), 367-37 Google Scholar
- 16 JOHNSON, D BEfficient algorithms for shortest paths m sparse networks J ACM 24, 1 (Jan. 1977), 1--13. Google Scholar
- 17 KENNEDY, K W Node hstmgs apphed to data flow analysis Conf. Rec 2nd ACM Symp. on Principles of Programmmg Languages, Palo Alto, Cahf., 1975, pp. 10--21. Google Scholar
- 18 KLEENE, S.C. Representation of events in nerve nets and finite automata. In Automata Studies, C Shannon and J McCarthy, Eds, Prmceton Untverstty Press, Princeton, N J, 1956, pp 3-40Google Scholar
- 19 KNUTH, D.E The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison- Wesley, Readmg, Mass, 1968, pp 258-265. Google Scholar
- 20 KNUTH, D E. An empmcal study of FORTRAN programs. Soflw Pract and Exper. 1 (1971), 105-133Google Scholar
- 21 LENGAUER, T, AND TAR/AN, R E. A fast algorithm for finding dominators m a flowgraph. Trans. Prog Lang and Syst 1, 1 (July 1979), 121-141 Google Scholar
- 22 ROSE, D J, SHERMAN, A.H, TARJAN, R E., AND WHITTEN, G.F. Algortthms and software for m-core factonzatton of sparse symmetnc posttlve definite matrices. Comput. Struct 10 (1979), 411--418Google Scholar
- 23 SCHAEFER, M A Mathematical Theory of Global Program Opttmtzatwn Prentice-Hall, Englewood Chffs, N.J, 1973 Google Scholar
- 24 TARJAN, R E. Depth-first search and hnear graph algorithms SIAM J Comput 1 (1972), 146-160Google Scholar
- 25 TARJAN, R E Finding dominators m &rected graphs SIAM J Comput 3 (1974), 62-89Google Scholar
- 26 TARJAN, R E Testmg flow graph reducibility J Comput and Syst Sct. 9 (1974), 355-365.Google Scholar
- 27 TARJAN, R E.Solvmg path problems on dtrected graphs Tech. Rep STAN-CS-75-528, Computer Science Dep, Stanford Umv, Stanford, Cahf., 1975. Google Scholar
- 28 TARJAN, R.E Graph theory and Gausstan ehmmauon In Sparse Mamx Computatwns, J R Bunch and D.J. Rose, Eds., Academic Press, New York, 1976 pp. 3-22Google Scholar
- 29 TARJAN, R E Apphcattons of path compresston on balanced trees J ACM 26, 4 (Oct 1979), 690-715 Google Scholar
- 30 TARJAN, R E. A untried approach to path problems J ACM 28, 3 (July 1981), 577-593. Google Scholar
- 31 ULLMAN, J.D Fast algorithms for the ehmmatton of common subexpresslons. Acta Inform 2 (1973), 191-213Google Scholar
Index Terms
- Fast Algorithms for Solving Path Problems
Recommendations
Solving dynamic constraint optimization problems using ICHEA
ICONIP'12: Proceedings of the 19th international conference on Neural Information Processing - Volume Part IIIMany real-world constrained problems have a set of predefined static constraints that can be solved by evolutionary algorithms (EAs) whereas some problems have dynamic constraints that may change over time or may be received by the problem solver at run ...
Lagrangian relaxation and enumeration for solving constrained shortest-path problems
The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian ...
Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems
WI-IAT '15: Proceedings of the 2015 IEEE / WIC / ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT) - Volume 01Distributed constraint optimization (DCOP) problems are well-suited for modeling multi-agent coordination problems. However, it only models static problems, which do not change over time. Consequently, researchers have introduced the Dynamic DCOP (DDCOP)...
Comments