Multi-processor scheduling and expanders. (English) Zbl 0820.68020
Summary: We prove that the non-existence of expanders with high expansion implies the existence of an ideal \(p\)-processor scheduling for directed acyclic graphs (dags) with maximum in-degree \(d\) and all levels of size greater than \((1+ (2\ln \ln d)/\ln d) (d/\ln d)p\) for sufficiently large \(d\) and \(p\).
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68M10 | Network design and communication in computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Ajtai, M.; Komlos, J.; Szemeredi, E., Sorting in \(c\) log \(n\) parallel steps, Combinatorica, 3, 1-19 (1983) · Zbl 0523.68048 |
| [2] | Alon, N.; Galil, Z.; Milman, V. D., Better expanders and superconcentrators, J. Algorithms, 8, 337-347 (1987) · Zbl 0641.68102 |
| [3] | Arora, S.; Leighton, T.; Maggs, B., On-line algorithms for path selection in a non-blocking network, Proc. 22nd STOC, 149-158 (1990) |
| [4] | Bassalygo, L. A., Asymptotically optimal switching circuits, Problems Inform. Transmission, 17, 206-211 (1981) · Zbl 0486.94021 |
| [5] | Blum, M.; Karp, R. M.; Vornberger, O.; Papadimitriou, C. H.; Yannakakis, M., The complexity of testing whether a graph is a superconcentrator, Inform. Process. Lett., 13, 164-167 (1981) · Zbl 0482.05059 |
| [6] | Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processor systems, Acta Inform., 1, 200-213 (1972) · Zbl 0248.68023 |
| [7] | Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Co: W.H. Freeman and Co San Francisco · Zbl 0411.68039 |
| [8] | Hu, T. C., Parallel sequencing and assembly line problem, Oper. Res., 9, 841-848 (1961) |
| [9] | Kahale, N., Better expansion for Ramanujan graphs, Proc. 32nd FOCS, 398-404 (1991) |
| [10] | Leighton, T.; Maggs, B., Expanders might be practical: Fast algorithms for routing around faults in multibutter-flies, 30th Proc. FOCS, 384-389 (1989) |
| [11] | Lubotsky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-278 (1988) · Zbl 0661.05035 |
| [12] | Margulis, G. A., Explicit constructions of concentrators, Problems of Inform. Transmission, 9, 325-332 (1975) |
| [13] | Pinsker, M., On the complexity of a concentrator, Proc. 7th Internat. Teletraffic Conf., 318/1-318/4 (1973), Stockholm |
| [14] | Pippenger, N., Superconcentrators, SIAM J. Comput., 6, 298-304 (1977) · Zbl 0361.05035 |
| [15] | Rudin, W. H., Real and Complex Analysis (1974), Mc-Graw Hill: Mc-Graw Hill New York · Zbl 0278.26001 |
| [16] | Valiant, L., Graph theoretic properties in computational complexity, J. Comput. System Sci., 13, 278-285 (1976) · Zbl 0354.68071 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
