Show simple item record

A relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent set

dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-14T10:11:43Z
dc.date.available2010-01-14T10:11:43Z
dc.date.issued1994
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2928
dc.description.abstractfrSoit ρ une constante universelle représentant le rapport d'approximation d'un algorithme approché hypothétique pour les instances du problème du stable maximum vérifiant 9/20 n ≤ α(G) ≤ 11/20 n où G est un graphe d'ordre n et de nombre de stabilité α(G). Supposons qu'il existe un algorithme approché de rapport constant pour le problème de recouvrement minimum d'ensembles. Il existe alors un algorithme polynomial approché pour le problème de transversal minimum avec un rapport majoré par max {9/5, 2−9/10 ρ} + ε avec ε arbitrairement petiten
dc.language.isoenen
dc.subjectProblème transversalen
dc.subjectNP complete problemen
dc.subjectGraph theoryen
dc.subjectThéorie grapheen
dc.subjectMéthode approchéeen
dc.subjectApproximate methoden
dc.subjectProblème NP completen
dc.subjectTemps polynomialen
dc.subjectPolynomial timeen
dc.subject.ddc003en
dc.titleA relation between the approximated versions of minimum set covering, minimum vertex covering and maximum independent seten
dc.typeArticle accepté pour publication ou publié
dc.relation.isversionofjnlnameRAIRO
dc.relation.isversionofjnlvol28en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate1994
dc.relation.isversionofjnlpages413-433en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherEDP Sciencesen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail
Name:
publi180.pdf
Size:
159.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record