Shortest paths in directed planar graphs with negative lengths

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log² n)-time algorithm

Full text

Pdf (441 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 236-245

Year of Publication: 2009

Authors

Philip Klein	Brown University, Providence RI
Shay Mozes	Brown University, Providence RI
Oren Weimann	Massachusetts Institute of Technology, Cambridge, MA

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 98, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

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

ABSTRACT

We give an O(n log² n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires O(n log³ n) time and O(n log n) space.

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	Alok Aggarwal , Maria Klawe, Applications of generalized matrix searching to geometric algorithms, Discrete Applied Mathematics, v.27 n.1-2, p.3-23, May 1990 [doi>10.1016/0166-218X(90)90124-U]
	2	A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1):195--208, 1987.
	3	I. J. Cox , S. B. Rao , Y. Zhong, "Ratio Regions": A Technique for Image Segmentation, Proceedings of the 13th International Conference on Pattern Recognition, p.557, August 25-29, 1996 [doi>10.1109/ICPR.1996.546886]
	4	Yuval Emek , David Peleg , Liam Roditty, A near-linear time algorithm for computing replacement paths in planar directed graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.428-435, January 20-22, 2008, San Francisco, California
	5	Jittat Fakcharoenphol , Satish Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, Journal of Computer and System Sciences, v.72 n.5, p.868-889, August 2006 [doi>10.1016/j.jcss.2005.05.007]
	6	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]
	7	H. N. Gabow , R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, v.18 n.5, p.1013-1036, Oct. 1989 [doi>10.1137/0218069]
	8	Andrew V. Goldberg, Scaling Algorithms for the Shortest Paths Problem, SIAM Journal on Computing, v.24 n.3, p.494-504, June 1995 [doi>10.1137/S0097539792231179]
	9	Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
	10	H. Ishikawa and I. Jermyn. Region extraction from multiple images. In 8th IEEE International Conference on Computer Vision, pages 509--516, Los Alamitos, CA, USA, 2001. IEEE Computer Society.
	11	Ian H. Jermyn , Hiroshi Ishikawa, Globally Optimal Regions and Boundaries as Minimum Ratio Weight Cycles, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1075-1088, October 2001 [doi>10.1109/34.954599]
	12	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]
	13	Maria M. Klawe , Daniel J. Kleitman, An almost linear time algorithm for generalized matrix searching, SIAM Journal on Discrete Mathematics, v.3 n.1, p.81-97, Feb. 1990 [doi>10.1137/0403009]
	14	Philip N. Klein, Multiple-source shortest paths in planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	15	R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM Journal on Numerical Analysis, 16:346--358, 1979.
	16	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.
	17	Gary L Miller, Finding small simple cycle separators for 2-connected planar graphs, Journal of Computer and System Sciences, v.32 n.3, p.265-279, June 1986 [doi>10.1016/0022-0000(86)90030-9]
	18	Gary L. Miller, Flow in Planar Graphs with Multiple Sources and Sinks, SIAM Journal on Computing, v.24 n.5, p.1002-1017, Oct. 1995 [doi>10.1137/S0097539789162997]
	19	G. Monge. Mémoire sur la théorie des déblais et ramblais. Mém. Math. Phys. Acad. Roy. Sci. Paris, pages 666--704, 1781.
	20	Olga Veksler, Stereo Correspondence with Compact Windows via Minimum Ratio Cycle, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.12, p.1654-1660, December 2002 [doi>10.1109/TPAMI.2002.1114859]

CITED BY 2

	Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Homology flows, cohomology cuts, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Erin W. Chambers , Jeff Erickson , Amir Nayyeri, Minimum cuts and shortest homologous cycles, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark