Efficient Algorithms for the max k -vertex cover Problem
Della Croce, Federico; Paschos, Vangelis (2012), Efficient Algorithms for the max k -vertex cover Problem, in Beaten, Jos C.M.; Ball, Tom; De Boer, Frank S., Theoretical Computer Science 7th IFIP TC1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012, Proceedings, Springer : Berlin, p. 295-309. 10.1007/978-3-642-33475-7_21
Type
Communication / ConférenceDate
2012Conference title
7th IFIP TC1/WG 2.2 International Conference on Theoretical Computer Science, TCS 2012Conference date
2012-09Conference city
AmsterdamConference country
NetherlandsBook title
Theoretical Computer Science 7th IFIP TC1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012, ProceedingsBook author
Beaten, Jos C.M.; Ball, Tom; De Boer, Frank S.Publisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
7604Published in
Berlin
ISBN
978-3-642-33474-0
Number of pages
393Pages
295-309
Publication identifier
Metadata
Show full item recordAuthor(s)
Della Croce, FedericoPaschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We 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.Subjects / Keywords
max k -vertex coverRelated items
Showing items related by title and author.
-
Paschos, Vangelis; Della Croce, Federico (2014) Article accepté pour publication ou publié
-
Boria, Nicolas; Della Croce, Federico; Paschos, Vangelis (2014) Communication / Conférence
-
Baburin, Aleksei; Della Croce, Federico; Gimadi, Edward; Glazkov, Yuri; Paschos, Vangelis (2009) Article accepté pour publication ou publié
-
Kaminski, Marcin; Della Croce, Federico; Paschos, Vangelis (2007) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié