- Title
- Polynomial-time linear kernelization for cluster editing
- Creator
- Fellows, Michael; Langston, Michael; Rosamond, Frances; Shaw, Peter
- Resource Type
- report
- Date
- 2007
- Description
- 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 24k kernelization bound (and possibly a 6k kernelization bound).
- Subject
- algorithms and complexity; bioinformatics
- Identifier
- uon:2595
- Identifier
- http://hdl.handle.net/1959.13/29602
- Language
- eng
- Full Text
- Hits: 1672
- Visitors: 1777
- Downloads: 156
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Author final version (unpublished) | 151 KB | Adobe Acrobat PDF | View Details Download |