{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:06:28Z","timestamp":1743005188155,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054371","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"234-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Formal language constrained path problems"],"prefix":"10.1007","author":[{"given":"Chris","family":"Barrett","sequence":"first","affiliation":[]},{"given":"Riko","family":"Jacob","sequence":"additional","affiliation":[]},{"given":"Madhav","family":"Marathe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"22_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"R. K. Ahuja","year":"1993","unstructured":"R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993."},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren and D. Seese, \u201cEasy Problems for Tree-Decomposable Graphs,\u201d Journal of Algorithms, vol. 12, pp. 308\u2013340 (1991).","journal-title":"Journal of Algorithms"},{"key":"22_CR3","unstructured":"M. Ben-Akiva and S.R. Lerman, Discrete Choice Analysis, MIT Press Series in Transportation Studies, Cambridge, MA, 1985."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"V. Blue, J. Adler and G. List, \u201cReal-Time Multiple Objective Path Search for In-Vehicle Route Guidance Systems,\u201d Proc. 76th Annual Meeting of The Transportation Research Board, Washington, D.C. Paper No. 970944, January 1997.","DOI":"10.3141\/1588-02"},{"key":"22_CR5","unstructured":"A. Buchsbaum, P. Kanellakis and J. Vitter, \u201cA Data Structure for Arc Insertion and regular Path Finding,\u201d Proc. 1st ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 22\u201331."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"M. Cruz, A. Mendelzon and P. Wood, \u201cA Graphical Query Language Supporting Recursion,\u201d Proc. 9th ACM SIGMOD Conference on Management of Data San Francisco, CA, 1990, 1987, pp. 323\u2013330.","DOI":"10.1145\/38714.38749"},{"key":"22_CR7","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, McGraw-Hill Book Co., 1990."},{"key":"22_CR8","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman, San Francisco (1979)."},{"issue":"1","key":"22_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R. Hassin","year":"1992","unstructured":"R. Hassin, \u201cApproximation schemes for the restricted shortest path problem\u201d, Mathematics of Operations Research 17, 1 (1992), 36\u201342.","journal-title":"Mathematics of Operations Research"},{"key":"22_CR10","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley, Reading MA., 1979."},{"key":"22_CR11","unstructured":"R. Jacob, M. Marathe, and K. Nagel, Computational Experiences with Routing Algorithms for Realistic Traffic Networks, in preperation."},{"issue":"1","key":"22_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(77)90002-3","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, \u201cA Generalization of Dijkstra's Algorithm,\u201d Information Proc. Lett., 6(1), pp. 1\u20135, 1977.","journal-title":"Information Proc. Lett."},{"issue":"No.6","key":"22_CR13","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"A. Mendelzon","year":"1995","unstructured":"A. Mendelzon and P. Wood, \u201cFinding Regular Simple Paths in Graph Databases,\u201d SIAM J. Computing, vol. 24, No. 6, 1995, pp. 1235\u20131258.","journal-title":"SIAM J. Computing"},{"key":"22_CR14","unstructured":"K. Scott, G. Pabon-Jimenez and D. Bernstein, \u201cFinding Alternatives to the Best Path,\u201d Proc. 76th Annual Meeting of The Transportation Research Board, Washington, D.C. Paper No. 970682, Jan. '97. Also available as Draft Report Intelligent Transport Systems Program, Princeton University, '97."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkh\u00c4user, 1994.","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"22_CR16","unstructured":"C. Barrett, K. Birkbigler, L. Smith, V. Loose, R. Beckman, J. Davis, D. Roberts and M. Williams, An Operational Description of TRANSIMS, Technical Report, LA-UR-95-2393, Los Alamos National Laboratory, 1995."},{"issue":"No.3","key":"22_CR17","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1145\/322261.322272","volume":"28","author":"R. Tarjan","year":"1981","unstructured":"R. Tarjan, \u201cA Unified Approach to Path Problems,\u201d J. ACM Vol. 28, No. 3, 1981, pp. 577\u2013593.","journal-title":"J. ACM"},{"issue":"No.3","key":"22_CR18","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"A. Orda","year":"1990","unstructured":"A. Orda and R. Rom, \u201cShortest Path and Minimium Delay Algorithms in Networks with Time Dependent Edge Lengths,\u201d J. ACM Vol. 37, No. 3, 1990, pp. 607\u2013625.","journal-title":"J. ACM"},{"issue":"2","key":"22_CR19","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"G. Ramalingam and T. Reps, \u201cAn incremental Algorithm for a Generalization of the Shortest-Path Problem,\u201d J. Algorithms, 21(2):267\u2013305, September 1996.","journal-title":"J. Algorithms"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"M. Yannakakis \u201cGraph Theoretic Methods in DataBase Theory,\u201d Proc. 9th ACM SIGACT-SIGMOD-SIGART Symposium on Database Systems (ACM-PODS), Nashville TN, 1990, pp. 230\u2013242.","DOI":"10.1145\/298514.298576"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T20:12:44Z","timestamp":1675714364000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0054371","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}