Reductions from problems to MIS, VC or Max. clique (info request)

Article View: comp.theory

Article #2121

#2121

From: Arun Jagota
Date: Fri, 02 Mar 1990 17:06

20 lines
1384 bytes

I would like to request references (or details if feasible) on
reductions FROM other problems (any and all) TO Maximum Independent
Set, Minimum cover or Maximum clique.
My interest is limited to reductions in which the representation is
explicitly shown (like the representation of 3-SAT in Vertex cover
in Gary & Johnson).
Indirect reductions (ie transitive closure) of such reductions is
fine too, as long as all the representations are made explicit along
the way.

Please reply to me, directly by "e-mail", unless you think an answer to 
this request is of general interest. I will compile all the information
I receive. Also to request any information that I've collected, send me 
e-mail. I prefer not clogging the net with information that may not have 
wide interest.

Thanking you,

Arun Jagota
jagota@cs.buffalo.edu

Technical Details

Message-ID: <18762@eerie.acsu.Buffalo.EDU>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!rpi!image.soe.clarkson.edu!sunybcs!sybil.cs.Buffalo.EDU

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!rpi!image.soe.clarkson.edu!sunybcs!sybil.cs.Buffalo.EDU
From: jagota@sybil.cs.Buffalo.EDU (Arun Jagota)
Newsgroups: comp.theory
Subject: Reductions from problems to MIS, VC or Max. clique (info request)
Message-ID: <18762@eerie.acsu.Buffalo.EDU>
Date: 2 Mar 90 17:06:12 GMT
Sender: nobody@acsu.Buffalo.EDU
Distribution: usa
Organization: State University of New York at Buffalo/Comp Sci
Lines: 20