Show simple item record

dc.contributor.authorToulouse, Sophie
HAL ID: 177689
ORCID: 0000-0002-6689-1008
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2009-10-03T07:57:23Z
dc.date.available2009-10-03T07:57:23Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2099
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectAPX-completeen
dc.subjectMaximum subgraph problemen
dc.subjectMinimum vertex deletion problemen
dc.subjectHereditary propertyen
dc.subject.ddc003en
dc.titleLocal approximations for maximum partial subgraph problemen
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 Letters
dc.relation.isversionofjnlvol32en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2004-05
dc.relation.isversionofjnlpages217-224en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.orl.2003.08.004en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record