13 Jun 1997 22:10:16 -0400

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) |

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.