Shortest path queries in planar graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shortest path queries in planar graphs

Full text

Pdf (1.13 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 469 - 478

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Danny Z. Chen	Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN
Jinhui Xu	Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 58, Citation Count: 4

Additional Information:

references cited by 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/335305.335359 What is a DOI?

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	A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, "Geometric Applications of a Matrix Searching Algorithm," Algorithmiea, Vol. 2, 1987, pp. 195-208.
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	Srinivasa Rao Arikati , Danny Z. Chen , L. Paul Chew , Gautam Das , Michiel H. M. Smid , Christos D. Zaroliagis, Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane, Proceedings of the Fourth Annual European Symposium on Algorithms, p.514-528, September 25-27, 1996
	4	C. Aydin and D. Ierardi, "Partitioning Algorithms for Transportation Graphs and Their Applications to Routing," Proe. of 9th Canadian Conference on Computational Geometry, 1997, pp.~245-250.
	5	Danny Z. Chen , Kevin S. Klenk , Hung-Yi T. Tu, Shortest path queries among weighted obstacles in the rectilinear plane, Proceedings of the eleventh annual symposium on Computational geometry, p.370-379, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220319]
	6	D.Z. Chen, D.T. Lee, R. Sridhar, and C.N. Sekharan, "Solving the All-Pair Shortest Path Query Problem on Interval and Circular-Arc Graphs," Networks, Vol. 31, No. 4, 1998, pp. 249-257.
	7	Shiva Chaudhuri , Christos D. Zaroliagis, Shortest Path Queries in Digraphs of Small Treewidth, Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, p.244-255, July 10-14, 1995
	8	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	9	H. Djidjev, G. Pantziou, and C. Zaroliagis, "On- Line and Dynamic Algorithms for Shortest Path Problems," Lecture Notes in Computer Science, Vol. 900, Springer-Verlag, Proc. 12th Syrup. on Theor. Aspects of Comp. $ci., 1995, pp. 193-204.
	10	E.W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numer. Math., Vol. 1, 1959, pp. 269-271.
	11	G.N. Frederickson, "Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications,'' SIAM Journal on Computing, Vol. 14, No. 4, 1985, pp. 781-798.
	12	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	13	Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
	14	Greg N. Frederickson, Using cellular graph embeddings in solving all pairs shortest paths problems, Journal of Algorithms, v.19 n.1, p.45-85, July 1995 [doi>10.1006/jagm.1995.1027]
	15	G.N. Frederickson, "Searching Intervals and Compact Routing Table," Algorithmica, Vol. 15, 1996, pp. 448-466.
	16	G.N. Frederickson and R. janardan, "Designing Networks with Compact Routing Tables," Algorithmica, Vol. 3, 1988, pp. 171-190.
	17	Greg N. Frederickson , Ravi Janardan, Space-efficient message routing in c-decomposable networks, SIAM Journal on Computing, v.19 n.1, p.164-181, Feb. 1990 [doi>10.1137/0219011]
	18	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	19	John Hershberger , Subhash Suri, Matrix searching with the shortest path metric, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.485-494, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167220]
	20	Yun-Wu Huang , Elke A. Rundensteiner, Query optimization for navigation in geographic information systems, 1997
	21	Y.W. Huang, N. Jing, and E.A. Rundensteiner, "A Semi-Materialized View Approach for Route Maintenance in IVHS," Proc. of 2nd A CM Workshop on Geographic Information Systems, 1994, pp. 144- 151.
	22	Y.W. Huang, N,. Jing, and E.A. Rundensteiner, "Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types," Proc. 3rd A CM Workshop on Geographic Information Systems, 1995, pp. 93-100.
	23	Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Effective graph clustering for path queries in digital map databases, Proceedings of the fifth international conference on Information and knowledge management, p.215-222, November 12-16, 1996, Rockville, Maryland, United States [doi>10.1145/238355.238497]
	24	Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195092]
	25	Dexter C. Kozen, The design and analysis of algorithms, Springer-Verlag New York, Inc., New York, NY, 1992
	26	E. Kranakis, D. Krizanc, and J. Urrutia, "Compact Routing and Shortest Path Information," Proc. ~nd Annual International Colloquium on Structure Information and Communication Complexity, 1995, L.M. Kirousis, and E. Kranakis (eds.), Carteton University Press, Vol. 2, 1996, pp. 101-112.
	27	R.J. Lipton and R.E. Taxjan, "A Separator Theorem for Planar Graphs," SIAM J. Appl. Math., Vol. 36, 1979, pp. 177-189.
	28	Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
	29	Shashi Shekhar , Ashim Kohli , Mark Coyle, Path Computation Algorithms for Advanced Traveller Information System (ATIS), Proceedings of the Ninth International Conference on Data Engineering, p.31-39, April 19-23, 1993

CITED BY 4

	Lukasz Kowalik , Maciej Kurowski, Short path queries in planar graphs in constant time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Sergio Cabello, Many distances in planar graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1213-1220, January 22-26, 2006, Miami, Florida
	Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004
	Lukasz Kowalik , Maciej Kurowski, Oracles for bounded-length shortest paths in planar graphs, ACM Transactions on Algorithms (TALG), v.2 n.3, p.335-363, July 2006