Name
Title | ||
|---|---|---|
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms |
Abstract | ||
|---|---|---|
Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, max independent set and min vertex cover. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.dam.2011.07.009 | Discrete Applied Mathematics |
Keywords | Field | DocType |
np-hard combinatorial problem,exact computation,worst-case complexity,min vertex cover,max independent set,approximation algorithm,polynomial time approximation,paradigmatic problem,exponential algorithm,min vertex,related problem,polynomial time,unlikely complexity conjecture,vertex cover,minimum vertex cover,independent set,maximum independent set,approximation algorithms | Discrete mathematics,Approximation algorithm,Combinatorics,Hardness of approximation,Edge cover,Independent set,Vertex cover,Time complexity,Conjecture,Feedback vertex set,Mathematics | Journal |
Volume | Issue | ISSN |
159 | 17 | 0166-218X |
Citations | PageRank | References |
24 | 0.73 | 27 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Bourgeois | 1 | 99 | 7.96 |
| Bruno Escoffier | 2 | 430 | 37.32 |
| Vangelis Th. Paschos | 3 | 633 | 63.97 |