Max. Indep. Set

Article View: comp.theory

Article #2010

#2010

From: Robert
Date: Wed, 10 Jan 1990 17:14

30 lines
1506 bytes

The following references may help. [3] has the best known approximation 
lgorithms. I have a polynomial-time algorithm for finding maximum (optimal)
independent sets of graphs that have no oddcycles that share an edge, in
case you are interested.

Bob

[1]   \s-2BAR-YEHUDA AND S. EVEN,\s+2 \f2A linear time approximation
algorithm for the weighted vertex cover problem\f1, J. Algorithms,
2(1981), pp. 198-203.
.XP
[2]   \s-2D. S. HOCHBAUM,\s+2 \f2Approximation algorithms for the
set covering and vertex cover problems\f1, Siam J. Comput.
11, no. 3 (1982), pp. 555-56.
.XP
[3]   \s-2B. MONIEN, AND E. SPECKENMEYER,\s+2 \f2Some Further Approximation Algorithms for the Vertex Cover Problem,\f1 Lecture Notes in
Computer Science 159 (1983) pp. 341-9.
.XP
[4]   \s-2C. SAVAGE\s+2, \f2Depth-First Search and the Vertex
Cover Problem\f1, Information Processing Letters, 14, no. 5, (1982).
Science, Gyor, (Hungary), 1983.
.XP
    Prof. Robert Levinson
    Computer and Information Sciences
    Applied Sciences Building
    University of California at Santa Cruz
    Santa Cruz, CA 95064
    (408)459-2087
    ARPANET:levinson@cis.ucsc.edu
       UUCP:ucbvax!ucsc!saturn!levinson

Technical Details

Message-ID: <10261@saturn.ucsc.edu>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!apple!agate!saturn!levinson

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!apple!agate!saturn!levinson
From: levinson@saturn.ucsc.edu (Robert)
Newsgroups: comp.theory
Subject: Max. Indep. Set
Message-ID: <10261@saturn.ucsc.edu>
Date: 10 Jan 90 17:14:18 GMT
Organization: U.C. Santa Cruz, CIS/CE.
Lines: 30