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
>