Write it recursively

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Write it recursively: a generic framework for optimal path queries

Full text

Pdf (266 KB)

Source

International Conference on Functional Programming archive
Proceeding of the 13th ACM SIGPLAN international conference on Functional programming table of contents

Victoria, BC, Canada

SESSION: Session 7 table of contents

Pages 169-178

Year of Publication: 2008

ISBN:978-1-59593-919-7

Also published in ...

Authors

Akimasa Morihata	University of Tokyo, Bunkyo-ku, Tokyo, Japan
Kiminori Matsuzaki	University of Tokyo, Bunkyo-ku, Tokyo, Japan
Masato Takeichi	University of Tokyo, Bunkyo-ku, Tokyo, Japan

Sponsors

ACM: Association for Computing Machinery
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 79, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1411204.1411229 What is a DOI?

ABSTRACT

Optimal path queries are queries to obtain an optimal path specified by a given criterion of optimality. There have been many studies to give efficient algorithms for classes of optimal path problem. In this paper, we propose a generic framework for optimal path queries. We offer a domain-specific language to describe optimal path queries, together with an algorithm to find an optimal path specified in our language. One of the most distinct features of our framework is the use of recursive functions to specify queries. Recursive functions reinforce expressiveness of our language so that we can describe many problems including known ones; thus, we need not learn existing results. Moreover, we can derive an efficient querying algorithm from the description of a query written in recursive functions. Our algorithm is a generalization of existing algorithms, and answers a query in O(n log n) time on a graph of O(n) size. We also explain our implementation of an optimal path querying system, and report some experimental results.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Chris Barrett , Riko Jacob , Madhav Marathe, Formal-Language-Constrained Path Problems, SIAM Journal on Computing, v.30 n.3, p.809-837, 2000 [doi>10.1137/S0097539798337716]
	2	Chris Barrett , Keith Bisset , Riko Jacob , Goran Konjevod , Madhav V. Marathe, Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router, Proceedings of the 10th Annual European Symposium on Algorithms, p.126-138, September 17-21, 2002
	3	Christopher L. Barrett, Keith Bisset, Riko Jacob, Goran Konjevod, Madhav V. Marathe, and Dorothea Wagner. Label constrained shortest path algorithms: An experimental evaluation using transportation networks. Technical report, Virginia Tech (USA), Arizona State University (USA), and Karlsruhe University (Germany), 2007.
	4	Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
	5	Gerth Stølting Brodal and Riko Jacob. Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theoretical Computer Science, 92:3--15, 2004.
	6	Edward P. F. Chan , Jie Zhang, A fast unified optimal route query evaluation algorithm, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321494]
	7	Oege De Moor , David Lacey , Eric Van Wyk, Universal Regular Path Queries, Higher-Order and Symbolic Computation, v.16 n.1-2, p.15-35, March-June 2003 [doi>10.1023/A:1023063919574]
	8	Martin Desrochers and François Soumis. A generalized permanent labeling algorithm for the shortest path problem with time windows. INFOR, 26:191--212, 1988.
	9	David Eppstein, Finding the k Shortest Paths, SIAM Journal on Computing, v.28 n.2, p.652-673, April 1999 [doi>10.1137/S0097539795290477]
	10	Sergio Flesca , Filippo Furfaro , Sergio Greco, Weighted path queries on semistructured databases, Information and Computation, v.204 n.5, p.679-696, May 2006 [doi>10.1016/j.ic.2005.12.002]
	11	Toshihide Ibaraki. Solvable classes of discrete dynamic programming. Journal of mathematical analysis and applications, 43(3):642--693, 1973.
	12	Toshihide Ibaraki. Branch-and-bound procedure and state-space representation of combinatorial optimization problems. Information and Control, 36(1):1--27, 1978.
	13	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
	14	H. C. Joksch. The shortest route problem with constraints. Journal of Mathematical analysis and applications, 14:191--197, 1966.
	15	Richard M. Karp and Michael Held. Finite-state processes and dynamic programming. SIAM Journal on Applied Mathematics, 15(3):693--718, 1967.
	16	Turgay Korkmaz and Marwan Krunz. Multi-constrained optimal path selection. In Proceedings IEEE INFOCOM 2001, The Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, pages 834--843, 2001.
	17	Yanhong A. Liu , Tom Rothamel , Fuxiang Yu , Scott D. Stoller , Nanjun Hu, Parametric regular path queries, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
	18	Ernesto Q. Vieira Martins. An algorithm for ranking paths that may contain cycles. European Journal of Operational Research, 18(1):123--130, 1984.
	19	Alberto O. Mendelzon , Peter T. Wood, Finding Regular Simple Paths in Graph Databases, SIAM Journal on Computing, v.24 n.6, p.1235-1258, Dec. 1995 [doi>10.1137/S009753979122370X]
	20	Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, and Masato Takeichi. Calculus of minimals: Deriving dynamic-programming algorithms based on preservation of monotonicity. Technical Report METR 2007-61, Department of Mathematical Informatics, University of Tokyo, 2007.
	21	Mizuhito Ogawa , Zhenjiang Hu , Isao Sasano, Iterative-free program analysis, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.111-123, August 25-29, 2003, Uppsala, Sweden
	22	Abraham P. Punnen. A linear time algorithm for the maximum capacity path problem. European Journal of Operational Research, 53(3):402--404, 1991.
	23	Jean-François Romeuf, Shortest path under rational constraint, Information Processing Letters, v.28 n.5, p.245-248, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90198-6]
	24	Isao Sasano , Zhenjiang Hu , Masato Takeichi , Mizuhito Ogawa, Make it practical: a generic linear-time algorithm for solving maximum-weightsum problems, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.137-149, September 2000
	25	Hanif D. Sherali , Chawalit Jeenanunta , Antoine G. Hobeika, The approach-dependent, time-dependent, label-constrained shortest path problem, Networks, v.48 n.2, p.57-67, September 2006 [doi>10.1002/net.v48:2]
	26	Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine. The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley, 2001.
	27	Daniel Villeneuve and Guy Desaulniers. The shortest path problem with forbidden paths. European Journal of Operational Research, 165(1):97--107, 2005.