Name
Abstract | ||
|---|---|---|
In the Cluster Editing problem, a graph is to be changed to a disjoint union of cliques by at most k operations of edge insertion or edge deletion. Improving on the best previously known quadratic-size polynomial-time kernelization, we describe how a crown-type structural reduction rule can be used to obtain a 6k kernelization bound. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74240-1_27 | FCT |
Keywords | Field | DocType |
polynomial time | Kernelization,Graph theory,Graph,Discrete mathematics,Combinatorics,Parameterized complexity,Computer science,Edge detection,Preprocessor,Vertex cover,Disjoint union | Conference |
Volume | ISSN | ISBN |
4639 | 0302-9743 | 3-540-74239-5 |
Citations | PageRank | References |
27 | 1.08 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Michael A. Langston | 2 | 1148 | 137.59 |
| Frances A. Rosamond | 3 | 304 | 15.94 |
| Peter Shaw | 4 | 92 | 6.34 |