An Almost-Linear Algorithm for Two-Processor Scheduling

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Almost-Linear Algorithm for Two-Processor Scheduling

Full text

Pdf (814 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 3 (July 1982) table of contents

Pages: 766 - 780

Year of Publication: 1982

ISSN:0004-5411

Author

Harold N. Gabow

Department of Computer Science, University of Colorado, Boulder, CO

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 43, Citation Count: 11

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/322326.322335 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	AHO, A V, GAgEY, M R, AND ULLMAN, J D The transitive reduction of a directed graph. SIAM J Comput I (1972), 131-137
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	COFFMAN, E G JR, ED Computer and Job-Shop Scheduhng Theory Wiley, New York, 1976
	4	COFFMAN, E G JP., AND GRAHAM, R L Optimal scheduling for two-processor systems A cta lnf 1, 3 (1972), 200-213
	5	Funl, M, KASAML T, AND NINOMIYA, K Optimal sequencing of two eqmvalent processors SIAM j Appt Math 17, 4 (1969), 784-789 Erratum, SIAM J Appl Math 20 (1971), 141
	6	GABow, H N An almost-hnear algorithm for two-processor scheduling Tech Rep CU-CS-169-80, Dep of Computer Science, Umv of Colorado, Boulder, Colo, Jan 1980
	7	GABOW, H.N Highest-level-first algorithms for approximate scheduhng In preparation
	8	M. R. Garey , D. S. Johnson, Scheduling Tasks with Nonuniform Deadlines on Two Processors, Journal of the ACM (JACM), v.23 n.3, p.461-467, July 1976 [doi>10.1145/321958.321967]
	9	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	10	GRAHAM, R L, LAWLER, E L, LENSTRA, J K, AND RINNOOY KAI% A H G Opum~zation and approximation in determmlsuc sequencing and scheduhng A survey Ann D~screte Math 5 (1979), 287-326
	11	Hu,TC Parallel sequencing and assembly line problems. Oper Res 9, 6 (1961), 841-848
	12	KARlV, O An O(n2~) algorithm for finding a maximum matching m a general graph Ph D Dissertation, Welzmann Institute of Science, Rehovot, Israel, 1976
	13	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	14	LAM, S, AND SETHI, R Worst case analysis of two scheduhng algorithms SlAM J Comput 6 (1977), 518-536
	15	MICALI, S, AND VAZIRANI, V V An O(,f{ V{. {EI) algorithm for finding maximum matching m general graphs Proc 21st Ann IEEE Symp on Foundations of Computer Science, Syracuse, N Y, Oct 1980, pp 17-27
	16	PAN, V Y Field extension and trlhnear aggregating, umtmg and cancelling for the acceleration of matrix multlphcaUons Proc 20th Ann IEEE Symp on Foundations of Computer Science, San Juan, Puerto Rico, Oct 1979, pp 28-38
	17	SEThi, R Scheduhng graphs on two processors SIAM ~ Comput 5, 1 (1976), 73-82
	18	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	19	ULLMAN, J D NP-complete scheduhng problems J Comput Syst Scl 10(1975), 384-393
	20	VAN EMDE BOAS, P, KAAS, R, ANt) ZIILSTRA, E Design and tmplementauon of an eMc~ent priority queue Math Syst Theory i0 (1977), 99-127

CITED BY 11

	Bonnie Berger , Lenore Cowen, Complexity results and algorithms for {<,≤,=}-constrained scheduling, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.137-147, January 28-30, 1991, San Francisco, California, United States
	David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989
	U Vazirani , V V Vazirani, The two-processor scheduling problem is in R-NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.11-21, May 06-08, 1985, Providence, Rhode Island, United States
	Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999
	Hermann Jung , Maria Serna , Paul Spirakis, An efficient deterministic parallel algorithm for two processors precedence constraint scheduling, Theoretical Computer Science, v.292 n.3, p.639-652, 31 January 2003
	Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983
	K. K. Jain , V. Rajaraman, Lower and Upper Bounds on Time for Multiprocessor Optimal Schedules, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.879-886, August 1994
	Yoojin Chung , Kunsoo Park, An efficient parallel algorithm for scheduling interval ordered tasks, Journal of Complexity, v.19 n.4, p.597-609, August 2003
	Theodora A. Varvarigou , Vwani P. Roychowdhury , Thomas Kailath , Eugene Lawler, Scheduling In and Out Forests in the Presence of Communication Delays, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1065-1074, October 1996
	Hans Stadtherr, Scheduling interval orders with communication delays in parallel, Journal of Parallel and Distributed Computing, v.64 n.1, p.1-15, January 2004
	Hesham El-Rewini , Hesham H. Ali , Ted Lewis, Task Scheduling in Multiprocessing Systems, Computer, v.28 n.12, p.27-37, December 1995