Article View: comp.theory
Article #1996Re: Max Indep Set
From: Magnus M Halldorsson
Date: Mon, 08 Jan 1990 17:58
Date: Mon, 08 Jan 1990 17:58
12 lines
897 bytes
897 bytes
In article <9001072141.AA22393@porthos.rutgers.edu> lucas@PSUVAX1.BITNET writes: > Does anyone have pointers to a practical approximation > algorithm for the maximum independent set problem? If you're looking for *performance guarantees* on general graphs, you're out of luck: there are no polynomial algorithms known. If you're thinking about good average case behaviour, the greedy method does within a factor of 2 on random graphs. Magnus
Technical Details
Message-ID:
<Jan.8.12.58.58.1990.25452@paul.rutgers.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!rutgers!aramis.rutgers.edu!paul.rutgers.edu!halldorsReferences:
<9001072141.AA22393@porthos.rutgers.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!rutgers!aramis.rutgers.edu!paul.rutgers.edu!halldors From: halldors@paul.rutgers.edu (Magnus M Halldorsson) Newsgroups: comp.theory Subject: Re: Max Indep Set Message-ID: <Jan.8.12.58.58.1990.25452@paul.rutgers.edu> Date: 8 Jan 90 17:58:59 GMT References: <9001072141.AA22393@porthos.rutgers.edu> Organization: Rutgers Univ., New Brunswick, N.J. Lines: 12