Show simple item record

dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorToulouse, S.
dc.date.accessioned2020-05-15T13:41:26Z
dc.date.available2020-05-15T13:41:26Z
dc.date.issued2003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20747
dc.language.isoenen
dc.subjectHereditary property
dc.subjectAPX-complete
dc.subjectMaximum subgraph problem
dc.subjectMinimum vertex deletion problem
dc.subjectAproximation algorithms
dc.subjectLocal search
dc.subject.ddc005en
dc.titleLocal approximation for maximum H0-free partial subgraph problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe deal with max H0-free partial subgraph. We mainly prove that 3-locally optimal solutions achieve approximation ratio (d0+1)/(B+2+n0), where B is the maximum degree on G, d0 the minimum degree on H0, and n0 = (|V(H0)|+1)/d0. Next, we show that this ratio rises up to 3/(B+1) when H0 = K3. Finally, we provide hardness results for max K3-free partial subgraph.
dc.relation.isversionofjnlnameOperations Research Letter
dc.relation.isversionofjnlvol31
dc.relation.isversionofjnlissue3
dc.relation.isversionofjnldate2003
dc.relation.isversionofjnlpages195-201
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00003926
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenon
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2020-09-25T10:22:01Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record