A More Effective Linear Kernelization for Cluster Editing

DOI10.1007/978-3-540-74450-4_4MaRDI QIDQ3611894zbMATH OpenOpenAlexFDO

Authors Jiong Guo

Publication date 3 March 2009

Published in Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74450-4_4

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A more effective linear kernelization for cluster editing
• A 2k kernel for the cluster editing problem
• A \(2k\) kernel for the cluster editing problem
• Cluster editing with locally bounded modifications
• Efficient Parameterized Preprocessing for Cluster Editing

Cited in

(35)

• Closest 4-leaf power is fixed-parameter tractable
• A more effective linear kernelization for cluster editing
• Cluster editing problem for points on the real line: a polynomial time algorithm
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Branch-and-price for \(p\)-cluster editing
• Clustering with partial information
• Applying modular decomposition to parameterized cluster editing problems
• On the complexity of multi-parameterized cluster editing
• Cluster editing with locally bounded modifications revisited
• Cluster editing: kernelization based on edge cuts
• Reducing rank of the adjacency matrix by graph modification
• Reducing rank of the adjacency matrix by graph modification
• Editing graphs into few cliques: complexity, approximation, and kernelization schemes
• Improved Algorithms for Bicluster Editing
• Exact Algorithms for Cluster Editing: Evaluation and Experiments
• A \(2k\) kernel for the cluster editing problem
• A Problem Kernelization for Graph Packing
• Clustering with Partial Information
• Iterative Compression and Exact Algorithms
• A 2k kernel for the cluster editing problem
• A survey of the algorithmic aspects of modular decomposition
• Kernelization and parameterized complexity of star editing and union editing
• Branch-and-cut approaches for p-cluster editing
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Efficient Parameterized Preprocessing for Cluster Editing
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Polynomial kernels for 3-leaf power graph modification problems
• \((1,1)\)-cluster editing is polynomial-time solvable
• (Sub)linear kernels for edge modification problems towards structured graph classes
• Cluster editing with locally bounded modifications
• A cubic kernel for feedback vertex set and loop cutset
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter algorithms for cluster vertex deletion

This page was built for publication: A More Effective Linear Kernelization for Cluster Editing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3611894)