Scheduling task-tree with additive scales on parallel/distributed machines

1. B. Berger and L. Cowen, “Complexity Results and Algorithms for the {≤=}-Constrained Scheduling”, SODA, 1991, pp. 137–147.

   Google Scholar 

2. S. Bhatt and J. Cai, “Take a walk, Grow a Tree”, FOCS, 1988, pp. 469–478.

   Google Scholar 

3. S. Bhatt, F. Chung, T.Leighton, and A. Rosenberg, Optimal Simulations of Tree Machines, FOCS, 1986, pp. 274–282.

   Google Scholar 

4. S. Bhatt, D. Greenberg, T.Leighton, and P. Liu, Tight Bounds for On-line Tree Embeddings, SODA, 1990, pp. 344–350.

   Google Scholar 

5. M.Y. Chan, Embedding of Grids into Optimal Hypercubes, SIAM Journal on Computing, Vol 20, No 5, Oct., 1991, pp. 834–864.

   Article  Google Scholar 

6. X. Deng and E. Koutsoupias, “Competitive Implementation of Parallel Programs”, Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 455–461.

   Google Scholar 

7. A.L.Fisher and H.T.Kung, Synchronizing Large VLSI Array Processor, Proc. of 10th Annual IEEE/ACM Symposium on Computer Architecture,1983, pp.54–58.

   Google Scholar 

8. A. Feldmann, J. Sgall, and S. Teng, “Dynamic Scheduling on Parallel Machines”, FOCS 91, pp. 111–120.

   Google Scholar 

9. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to Theory of NP-Completeness. San Francisco, CA, Freeman Publishing Co., 1979.

   Google Scholar 

10. K. Hwang and F. A. Briggs, Computer Architecture and Parallel Processing, McGRAW-Hill International Editions, 1987.

    Google Scholar 

11. J. Hong, K. Melhorn, and A.L. Rosenberg, Cost trade-offs in graph embeddings, with applications, JACM, 30, 1983, pp. 709–728.

    Article  Google Scholar 

12. T. C. Hu. Parallel Sequencing and Assembly Line Problem, Operations Research, Vol. 9, Nov. 1961, pp. 841–848.

    Google Scholar 

13. C. Kaklamanis and G. Persiano, “Branch-and-Bound and Backtrack Search on Mesh-Connected Arrays and Processors”, 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 118–128.

    Google Scholar 

14. R.Koch, T. Leighton, B.Maggs, S.Rao, and A.Rosenberg, Work-Preserving Emulations of Fixed-Connection Networks, STOC, 1989, pp. 227–240.

    Google Scholar 

15. C.H. Papadimitriou and J.D. Ullman, A communication time tradeoff, SIAM J. of Computing, 16 (4), 1987, pp. 639–646.

    Article  Google Scholar 

16. C.H. Papadimitriou and M. Yannakakis, “Towards An Architecture-Independent Analysis of Parallel Algorithms”, 20th ACM STOC, 1988, pp 510–513.

    Google Scholar 

17. S. Phillips and J. Westbrook, “Online Load Balancing and Network Flow”, 25th ACM STOC, 1993, pp 402–411.

    Google Scholar 

18. A. Ranade, “Optimal Speed-up for Backtrack Search on a Butterfly Network”, 3-d Annual ACM Symposium on Parallel Algorithms and Architectures, 1991, pp. 40–48.

    Google Scholar 

19. D. Shmoys, J. Wein, and D. Williamson, “Scheduling Parallel Machine Online”, FOCS 91, pp. 131–140.

    Google Scholar 

20. A. Wagner, Embedding arbitrary binary trees in a Hypercube, J. of Parallel and Distributed Computing, 7, 1989, pp. 503–520.

    Article  Google Scholar 

21. I.-C. Wu and H.T. Kung, “Communication Complexity for Parallel Divide-and-Conquer”, FOCS 91, pp. 151–162.

    Google Scholar 

22. X.Yu and D.Ghosal, “Optimal Dynamic Scheduling of Task Tree on Constantdimensional Architectures”, 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992, pp. 138–146.

    Google Scholar 

Download references