Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 40 Issue 5, Nov. 1993

Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling
E. G. Coffman, Jr., M. R. Garey
Pages: 991-1018
DOI: 10.1145/174147.174148

On the communication complexity of distributed algebraic computation
Zhi-Quan Luo, John N. Tsitsiklis
Pages: 1019-1047
DOI: 10.1145/174147.174149

Kinodynamic motion planning
Bruce Donald, Patrick Xavier, John Canny, John Reif
Pages: 1048-1066
DOI: 10.1145/174147.174150

On the optimality of strategies for multiple join
Y. C. Tay
Pages: 1067-1086
DOI: 10.1145/174147.174151

The impossibility of implementing reliable communication in the face of crashes
Alan Fekete, Nancy Lynch, Yishay Mansour, John Spinelli
Pages: 1087-1107
DOI: 10.1145/174147.169676

Complexity and algorithms for reasoning about time: a graph-theoretic approach
Martin Charles Golumbic, Ron Shamir
Pages: 1108-1133
DOI: 10.1145/174147.169675

An algebraic theory of graph reduction
Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, Detlef Seese
Pages: 1134-1164
DOI: 10.1145/174147.169807

Dynamic programming and the graphical traveling salesman problem
Jean Fonlupt, Armand Nachef
Pages: 1165-1187
DOI: 10.1145/174147.169803

Parallel queues with resequencing
Alain Jean-Marie, Levent Gün
Pages: 1188-1208
DOI: 10.1145/174147.169748

Extremal scheduling of parallel processing with and without real-time constraints
François Baccelli, Zhen Liu, Don Towsley
Pages: 1209-1237
DOI: 10.1145/174147.169745

On the sojourn time distribution in a finite capacity processor shared queue
Charles Knessl
Pages: 1238-1301
DOI: 10.1145/174147.169736
We consider a processor shared M/M/1 queue that can accommodate at most a finite number K of customers. Using singular perturbation techniques, we construct asymptotic approximations to the...