Name
Abstract | ||
|---|---|---|
The enumerate-and-expand paradigm for solving NP-hard problems has been introduced and applied to some Vertex Cover variants in a recently published preliminary paper. In this paper we improve on the runtime for Connected Vertex Cover, obtaining a bound of O*(2.7606k), and use the technique in order to gain the fastest known method for counting the number of vertex covers in a graph, which takes O*(1.3803k) time. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11809678_29 | COCOON |
Keywords | Field | DocType |
vertex cover variant,connected vertex cover,new runtime bound,enumerate-and-expand paradigm,np-hard problem,fastest known method,preliminary paper,np hard problem,vertex cover | Graph theory,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Vertex (graph theory),Computer science,Edge cover,Vertex cover,Feedback vertex set | Conference |
Volume | ISSN | ISBN |
4112 | 0302-9743 | 3-540-36925-2 |
Citations | PageRank | References |
8 | 0.58 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Mölle | 1 | 175 | 10.17 |
| Stefan Richter | 2 | 176 | 9.96 |
| Peter Rossmanith | 3 | 1000 | 61.03 |