Finding a minimum weight K-link path in graphs with Monge property and applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding a minimum weight K-link path in graphs with Monge property and applications

Full text

Pdf (701 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the ninth annual symposium on Computational geometry table of contents

San Diego, California, United States

Pages: 189 - 197

Year of Publication: 1993

ISBN:0-89791-582-8

Authors

Alok Aggarwal
Baruch Schieber
Takashi Tokuyama

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 21, Citation Count: 7

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/160985.161135 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. Wilbur, Geometric Applications of a Matrix- Searching Algorithm, Algorithmica 2 (1987), 195- 208.
	2	A. Aggarwal and J. Park, Notes on Searching in Multidimensional Monotone Arrays, Proc. of ~gth FOCS (1988), 407-512.
	3	A. Aggarwal and T. Tokuyama, Consecutive Interpal Query and Dynamic Programming on Intervals, Preprint 1992.
	4	Takao Asano, Dynamic Programming on Intervals, Proceedings of the 2nd International Symposium on Algorithms, p.199-207, December 16-18, 1991
	5	W. Bein, L. Larmore, and J. Park, The d- Edge Shortest-Path Problem for a Monge Graph, Preprint, 1992.
	6	James E. Boyce , David P. Dobkin , Robert L. Drysdale, III , Leo J. Guibas, Finding extremal polygons, SIAM Journal on Computing, v.14 n.1, p.134-147, Feb. 1985 [doi>10.1137/0214011]
	7	Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142702]
	8	Richard Cole, Slowing down sorting networks to obtain faster sorting algorithms, Journal of the ACM (JACM), v.34 n.1, p.200-208, Jan. 1987 [doi>10.1145/7531.7537]
	9	Kwong-fai Chan , Tak-wah Lam, Finding least-weight subsequences with fewer processors, Proceedings of the international symposium on Algorithms, p.318-327, August 1990, Tokyo, Japan
	10	Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
	11	Maria M. Klawe, A Simple Linear Time Algorithm for Concave One-Dimensional Dynamic Programming, University of British Columbia, Vancouver, BC, Canada, 1989
	12	M. Klawe and D. Kleitman, An Almost Linear Time Algorithm for Generalized Matrix, Technical Report tL16275, IBM Almaden Research Center, 1988.
	13	Lawrence L. Larmore , Daniel S. Hirschberg, Length-limited coding, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.310-318, January 22-24, 1990, San Francisco, California, United States
	14	Lawrence L. Larmore , Teresa M. Przytycka, Parallel construction of trees with optimal weighted path length, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.71-80, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113386]
	15	Lawrence L. Larmore , Baruch Schieber, On-line dynamic programming with applications to the prediction of RNA secondary structure, Journal of Algorithms, v.12 n.3, p.490-515, Sept. 1991 [doi>10.1016/0196-6774(91)90016-R]
	16	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983 [doi>10.1145/2157.322410]
	17	L. Valiant, Parallelism in Comparison Problems, SIAM J. Comput. 4 (1975), 348-355.
	18	Xiaolin Wu, Optimal quantization by matrix searching, Journal of Algorithms, v.12 n.4, p.663-673, Dec. 1991 [doi>10.1016/0196-6774(91)90039-2]

CITED BY 7

	Xiaobo Sharon Hu , Danny Z. Chen , Rajeshkumar Sambandam, Efficient list-approximation techniques for floorplan area minimization, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.372-400, July 2001
	Danny Z. Chen , Xiaobo Hu, Efficient approximation algorithms for floorplan area minimization, Proceedings of the 33rd annual conference on Design automation, p.483-486, June 03-07, 1996, Las Vegas, Nevada, United States
	Magnús M. Halldórsson , Kazuo Iwano , Naoki Katoh , Takeshi Tokuyama, Finding subsets maximizing minimum structures, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.150-159, January 22-24, 1995, San Francisco, California, United States
	Owen Kaser, Optimal height reduction problems for tree-structured hierarchies, Nordic Journal of Computing, v.4 n.4, p.357-379, Winter 1997
	Wolfgang Bein , Peter Brucker , Lawrence L. Larmore , James K. Park, The algebraic Monge property and path problems, Discrete Applied Mathematics, v.145 n.3, p.455-464, 30 January 2005
	Himanshu Gupta , Rephael Wenger, Constructing pairwise disjoint paths with few links, ACM Transactions on Algorithms (TALG), v.3 n.3, p.26-es, August 2007
	Alexander Schliep , Roland Krause, Efficient Algorithms for the Computational Design of Optimal Tiling Arrays, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.4, p.557-567, October 2008