graph coloring (Waleed Meleis)
13 Jun 1997 22:10:16 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: graph coloring (Robert Thorpe) (2004-02-08)
Re: graph coloring (John McEnerney) (2004-02-12)
Re: Graph Coloring (TOUATI Sid) (2004-02-12)
graph coloring (Ramesh B S) (1996-03-20)
Re: graph coloring (David Gillies) (1996-03-22)
Re: graph coloring (1996-03-25)
graph coloring (1997-06-13)
| List of all articles for this month |

From: (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


Waleed Meleis

Post a followup to this message

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