Polynomial-time linear kernelization for cluster editing | NOVA. The University of Newcastle's Digital Repository

Home

Description	Size	Format
Author final version (unpublished)	151 KB	Adobe Acrobat PDF	View/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/29602

Title: Polynomial-time linear kernelization for cluster editing
Author/Creator: Fellows, Michael; Langston, Michael; Rosamond, Frances; Shaw, Peter
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).
Date: 2007
Keyword(s): algorithms and complexity; bioinformatics
Resource Type: report
Identifier: http://hdl.handle.net/1959.13/29602
Language: eng

25 Visitors

37 Hits

NOVA. The University of Newcastle's Digital Repository