An implementation of the &egr;-relaxation algorithm on the CM-5

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An implementation of the &egr;-relaxation algorithm on the CM-5

Full text

Pdf (914 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 183 - 192

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

B. Narendran
Renato De Leone
Prasoon Tiwari

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	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/165231.165255 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.

	AS92	Richard J. Anderson , João C. Setubal, On the parallel implementation of Goldberg's maximum flow algorithm, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.168-177, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140919]
	BCJL91	R.G. Bland, J. Cheriyan, D. L. jensen, and L. Lad~nyi. An Empirical Study of Recent Min Cost Flow Algorithms. In DIMACS Series in Discrete Mathematics. American Mathematical Society, 1991. To Appear.
	Ber91	Dimitri P. Bertsekas, Linear network optimization: algorithms and codes, MIT Press, Cambridge, MA, 1991
	BT89	Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	CLP92	1%. Cerulli, R. De Leone, and G. Piacente. A Modified Auction Algorithm for the Shortest Path Problem. Technical Report 1113, Computer Sciences Department , University of Wisconsin-Madison, October 1992.
	Eck87	J. Eckstein. Implementing and Running the Alternating Step Method on the Connection Machine, November 1987.
	FINT91	S. Pujishige, K. Iwano, J. Nakano, and S. Tezuka. A Speculative Contraction Method for Minimum Cost Flows: Toward a Practical Algorithm. Presented at the DI- MACS Implementation Challenge, August 1991.
	GHR91	R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. A Compendium of Problems Complete for P. Technical Report TR 91-05-01, Department of Computer Science and Engineering, University of Washington, December 1991.
	GK92	A. Gupta and V. Kumar. Scalability of Parallel Algorithms for Matrix Multiplication. Manuscript, 1992.
	Gol87	A. V. Goldberg. Efficient Graph Algorithms for Sequential and Parallel Computers. PhD thesis, M.I.T., 1987.
	GSS82	L. M. Goldschlager, R. A. Shaw, and J. Staples. The Maximum Flow Problem is log space complete for P. Theoretical Computer Science, 21:105-111, 1982.
	GT90	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990
	Kar78	R. M. Karp. A Characterization of the Minimum Cycle Mean in a Digraph. Discrete Mathematics, 23:309-311, 1978.
	KO81	R.M. Karp and J.B. Orlin. Parametric Shortest Path Algorithms with an Application to Cyclic Staffing. Discrete Applied Mathematics, 3:37-45, 1981.
	LO91	Y. Lee and j. B. Orlin. Computational Testing of a Network Simplex Algorithm. Presented at the DIMACS Implementation Challenge, 1991.
	LW87	T. Lengauer , K. W. Wagner, The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems, 4th Annual Symposium on Theoretical Aspects of Computer Sciences on STACS 87, p.100-113, February 1987, Passau, Germany
	LZ91a	X. Li and S. A. Zenios. Data-level Parallel Solution of Min-cost Network Flow Problems Using e-Relaxations. Technical Report 91-05-04, Department of Decision Sciences, The Wharton School, University of Pennsylvania, May 1991.
	LZ91b	X. Li and S. A. Zenios. Massively Parallel e-Relaxation Algorithms for Linear Transportation Problems. To be Presented at the 1991 International Conference on Parallel Processing, 1991.
	NA91	Daniel Nussbaum , Anant Agarwal, Scalability of parallel machines, Communications of the ACM, v.34 n.3, p.57-61, March 1991 [doi>10.1145/102868.102871]
	NLT93	B. Narendran, Renato De Leone, and Prasoon Tiwari. Parallel Computation of Min- Cost Flows on the CM-5. Technical Report (in preparation), 1993.
	NZ91	S. S. Nielsen and S. A. Zenios. Proximal Minimizations with D-Functions and the Massively Parallel Solution of Linear Programs. Technical Report 91-06-05, Department of Decision Sciences, The Wharton School, University of Pennsylvania, October 1991.
	Orl88	James Orlin, A faster strongly polynomial minimum cost flow algorithm, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.377-387, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62249]
	Pet88	:I. Peters. A Parallel Algorithm for Minimal Cost Network Flow Problems. Technical Report 762, Computer Sciences Department, University of Wisconsin-Madison, April 1988.
	PZ89	C. Philllp8 and S. A. Zen\|o#. Experlence# with Large Scale Network Optimization on the Connection Machine. In B. L. Golden, E. Wasil, O. Balci, and W. Stewart, editors, Impact of Recent Computer Advances on Operations Research, pages 169-180. Elsevier Science Publishing Co., 1989.
	SW91	C. Stein and J. Wein. Approximating the Minimum Cost Maximum Flow is P- complete. Manuscript, September 1991.
	Tar83	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	vECGS92	Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
	WZ91	Joel M. Wein , Stavros A. Zenios, On the massively parallel solution of the assignment problem, Journal of Parallel and Distributed Computing, v.13 n.2, p.228-236, Oct. 1991 [doi>10.1016/0743-7315(91)90092-N]