Vazirani, Umesh V.Vazirani, Vijay V.2007-04-232007-04-231989-05http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1000https://hdl.handle.net/1813/6800An efficient parallel algorithm $(RNC^{2})$ for the two-processor scheduling problem is presented. An interesting feature of this algorithm is that it finds a highest level first schedule: such a schedule defines a lexicographically first solution to this problem in a natural way. A key ingredient of the algorithm is a generalization of a theorem of Tutte which establishes a one-to-one correspondence between the bases of the Tutte matrix of a graph and the sets of matches nodes in maximum matchings in the graph.1233340 bytes291708 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report