Show simple item record

dc.contributor.authorDella Croce, Federico*
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2013-09-05T10:56:08Z
dc.date.available2013-09-05T10:56:08Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11618
dc.language.isoenen
dc.subjectmax k -vertex coveren
dc.subject.ddc003en
dc.titleEfficient Algorithms for the max k -vertex cover Problemen
dc.typeCommunication / Conférence
dc.description.abstractenWe first devise moderately exponential exact algorithms for max k -vertex cover, with time-complexity exponential in n but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max k -vertex cover with complexity bounded above by the maximum among c k and γ τ , for some γ < 2, where τ is the cardinality of a minimum vertex cover of G (note that \textsc{maxk-vertex cover}{} \notin \textbf{FPT} with respect to parameter k unless FPT=W[1] ), using polynomial space. We finally study approximation of max k -vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.en
dc.identifier.citationpages295-309en
dc.relation.ispartofseriestitleLecture Notes in Computer Scienceen
dc.relation.ispartofseriesnumber7604en
dc.relation.ispartoftitleTheoretical Computer Science 7th IFIP TC1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012, Proceedingsen
dc.relation.ispartofeditorBeaten, Jos C.M.
dc.relation.ispartofeditorBall, Tom
dc.relation.ispartofeditorDe Boer, Frank S.
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2012
dc.relation.ispartofpages393en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-33475-7en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-33474-0en
dc.relation.conftitle7th IFIP TC1/WG 2.2 International Conference on Theoretical Computer Science, TCS 2012en
dc.relation.confdate2012-09
dc.relation.confcityAmsterdamen
dc.relation.confcountryNetherlandsen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-33475-7_21en
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds*
hal.person.labIds989*
hal.identifierhal-01511883*


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