Max Indep Set

Article View: comp.theory

Article #2007

#2007

From: Patrick Healy
Date: Wed, 10 Jan 1990 15:21

14 lines
951 bytes

>        Does anyone have pointers to a practical approximation
>algorithm for the maximum independent set problem?

>                                Thanks,  Joan Lucas


I would be interested in approximation algorithms (or references) to the
weighted version of ths problem i.e., Maximum Weighted Independent Set.  I've
seen references to some special cases of the related problem: Maximum Weighted
Clique, but nothing for the general case.

Any pointers would be appreciated.  Thanks,
Pat Healy,
Univ. of Mass, Amherst.

Technical Details

Message-ID: <9001101346.AA00598@okane.cs.umass.edu>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!OKANE.CS.UMASS.EDU!patrick

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!OKANE.CS.UMASS.EDU!patrick
From: patrick@OKANE.CS.UMASS.EDU (Patrick Healy)
Newsgroups: comp.theory
Subject: Max Indep Set
Message-ID: <9001101346.AA00598@okane.cs.umass.edu>
Date: 10 Jan 90 15:21:52 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Patrick Healy <patrick%okane.cs.umass.edu@VM1.NoDak.EDU>
Lines: 14