From goldberg@cs.rpi.edu Tue Sep 17 22:34:30 1996 From: goldberg@cs.rpi.edu Date: Tue, 17 Sep 96 22:28:34 EDT To: skiena@sbcs.sunysb.edu Subject: edge-coloring Status: RO Steve, My next message contains a C-program for edge coloring. It is simple and short, but I didn't test it enough to be sure in it. It can be applied to any multigraph and will determine if the multigraph has a Delat coloring where Delta is the max degree. Two other programs are in PERL: they generate random and random-regular graphs. Hope it is useful. Please let me know how they performed. Best, -Mark From goldberg@cs.rpi.edu Wed Sep 25 23:34:41 1996 From: goldberg@cs.rpi.edu Date: Wed, 25 Sep 96 23:31:28 EDT To: skiena@cs.sunysb.edu Subject: Re: edge-coloring Cc: goldberg@cs.rpi.edu Status: RO Steve, No objections, but I think my student, Amir Sehic, and I should be acknowledged. Amir (he is from Boshia) left RPI; the program and experiments were his MS programming project which is a requirement. The algorithm and many details of the program were proposed by me. The output, in fact, is much richer than just the coloring: it also gives (unless in your version, the corresponding part is commented out) the "deviation" of the resulting coloring from the greedy coloring. The point of the project was to experimenatlly establish that the deviation is "small". Best, -Mark > Mark, > thanks for the files. I will put them on our WWW site soon, > so I will assume you have no objections if I put them there or on the > associated CD-ROM -- let me know otherwise. > > Thanks > Steve >