graph coloring

meleis@ece.neu.edu (Waleed Meleis)
13 Jun 1997 22:10:16 -0400

          From comp.compilers
Related articles
[2 earlier articles]
Re: graph coloring Robert.Thorpe@antenova.com (Robert Thorpe) (2004-02-08)
Re: graph coloring jmcenerney@austin.rr.com (John McEnerney) (2004-02-12)
Re: Graph Coloring touati@prism.uvsq.fr (TOUATI Sid) (2004-02-12)
graph coloring bsr@cs.clemson.edu (Ramesh B S) (1996-03-20)
Re: graph coloring dgillies@hpax.cup.hp.com (David Gillies) (1996-03-22)
Re: graph coloring napi@ms.mimos.my (1996-03-25)
graph coloring meleis@ece.neu.edu (1997-06-13)
| List of all articles for this month |
From: meleis@ece.neu.edu (Waleed Meleis)
Newsgroups: comp.compilers
Date: 13 Jun 1997 22:10:16 -0400
Organization: Compilers Central
Keywords: theory, question

I'm looking for an optimal algorithm to solve the following two graph
coloring problems:


Given a graph and a fixed number of colors:


  find a subset of the nodes, and an assignment of colors to the nodes in
  that subset, such that adjacent nodes are assigned different colors and
  such that one of the two following objective functions is maximized:


  1) the number of nodes in the subset, or
  2) the sum of the degrees of the nodes in the subset.




Any suggestions or pointers relating to these problems would be
appreciated.


Thanks,


Waleed Meleis
meleis@ece.neu.edu
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.