Kubale, Marek The complexity of scheduling independent two-processor tasks on dedicated processors. (English) Zbl 0653.68015 Inf. Process. Lett. 24, 141-147 (1987). Cited in 24 Documents MSC: 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems 68Q25 Analysis of algorithms and problem complexity 68N25 Theory of operating systems Keywords:computational complexity; edge coloring; NP-completeness; two-processor task scheduling PDFBibTeX XMLCite \textit{M. Kubale}, Inf. Process. Lett. 24, 141--147 (1987; Zbl 0653.68015) Full Text: DOI References: [1] Błażewicz, J.; Wȩglarz, J.; Drabowski, M., Scheduling independent 2-processor tasks to minimize schedule length, Inform. Process. Lett., 18, 267-273 (1984) · Zbl 0544.68032 [2] Błażewicz, J.; Drabowski, M.; Wȩglarz, J., Scheduling multi-processor tasks to minimize schedule length, IEEE Trans. Comput., C-35, 389-393 (1986) · Zbl 0604.68040 [3] Coffman, E. G.; Garey, M. R.; Johnson, D. S.; LaPaugh, A. S., Scheduling file transfers in a distributed network, (Proc. 2nd ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (1983), ACM: ACM New York), 254-266 [4] Cole, R.; Hopcroft, J. E., On edge coloring bipartite graphs, SIAM J. Comput., 11, 540-546 (1982) · Zbl 0486.68062 [5] Dolev, D.; Simons, B.; Warmuth, M., Procrastination pays: A mixed scheduling strategy (1982), Unpublished manuscript [6] Gabow, H. N.; Nishizeki, T.; Kariv, O.; Leven, D.; Terada, O., Algorithms for edge-coloring graphs (1984), Unpublished manuscript [7] Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034 [8] Krawczyk, H.; Kubale, M., An approximation algorithm for diagnostic test scheduling in multicomputer systems, IEEE Trans. Comput., C-34, 869-872 (1985) [9] Kubale, M., Algorithms for 1.5 edge-coloring of binomial trees and unicyclic graphs (1985), Unpublished manuscript [10] Kubale, M., Interval edge-coloring of caterpillars with hairs of arbitrary length, (Proc. Internat. Conf. on Combinatorial Analysis and its Applications. Proc. Internat. Conf. on Combinatorial Analysis and its Applications, Pokrzywna (1985)), to appear · Zbl 0737.05048 [11] Mitchell, S.; Hedetniemi, S., Linear algorithms for edge-coloring trees and unicyclic graphs, Inform. Process. Lett., 9, 110-112 (1979) · Zbl 0415.68030 [12] Nishizeki, T.; Kashiwagi, K., An upper bound on the chromatic index of multigraphs, (Alavi, Y.; etal., Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York), 595-604 [13] Proskurowski, A.; Sysło, M. M., Edge-coloring of trees and unicyclic graphs, Ars Combinatoria, 16, 17-20 (1983) · Zbl 0539.05034 [14] Simons, B.; Sipser, M., On scheduling unit-length jobs with multiple release time/deadline intervals, Oper. Res., 32, 80-88 (1984) · Zbl 0531.90048 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.