A one-way array algorithm for matroid scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A one-way array algorithm for matroid scheduling

Full text

Pdf (779 KB)

Source

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

Hilton Head, South Carolina, United States

Pages: 349 - 356

Year of Publication: 1991

ISBN:0-89791-438-4

Author

Matthias F. M. Stallmann

Department of Computer Science, North Carolina State University, Raleigh, NC

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/113379.113411 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	M. AIGNER, Combinatorial Theory, Springer Verlag, 1979.
	2	S. ASHTAPUTaE AND C. SAVAGE, Systolic arrays with embedded tree structures for connectivity problems, IEEE Transactions on Computers, C-34 (1985), pp. 483- 484.
	3	G. N. FREDEaICKSON, Scheduling unit-time tasks with integer release times and deadlines, Inf. Process Lett., 16 (1983), pp. 171 173.
	4	Greg N. Frederickson , Mandayam A. Srinivas, On-line updating of solutions to a class of matroid intersection problems, Information and Computation, v.74 n.2, p.113-139, Aug. 1987 [doi>10.1016/0890-5401(87)90027-7]
	5	H. N. GABOW AND P~. E. TARJAN, Efficient algorithms for a family of malroid inier,~eciion problems, Journal of Algorithms, 5 (1984), pp. 80- 131.
	6	------, A linear-time algorithm for a special case of disjoint set union, J. Comput. System Set., 30 (1985), pp. 209 - 221.
	7	F. GLOVER, Maximum matching in a convex bipartile graph, Naval Research Logistics Quarterly, 14 (1967), pp. 313- 316.
	8	S. -T. Huang, A fully pipelined minimum-spanning-tree constructor, Journal of Parallel and Distributed Computing, v.9 n.1, p.55-62, May 1990 [doi>10.1016/0743-7315(90)90111-2]
	9	E. L. LAWLEa, Combinatorial Obptimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
	10	W. LIPSKI, JR. AND F. P. PREPARATA, Efficient algorithms for finding maximum malchings zn convex bzpartite graphs and relat,o.d problems, Acta Inf., 15 (1981), pp. 329- 346.
	11	C. SAVAGE, M. STALLMANN, AND J. PERRY, Solving some combinatorial problems on arrays with one-way dataflow, Algorithmica, 5 (1990), pp. 179- 199.
	12	C. D. SAVAGE, M. F. STALLMANN, AND i. Z. KOTOB, Simulation of lwo-way computations on arrays with one-way data flow, Tech. Rep. CCSP- TR-87/6, North Carolina State University Center for Communications and Signal Processing, 1987.
	13	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	14	M. TCHUENTE AND L. MELKEMY, Reseaux 8ystoliques pour le calcul des composantes connexes et le lriangularisation des matrices bandes, Tech. Rep. 366, Laboratoire d'Informatique et de Mathematiques Appliquees de Grenoble, 1983.