Applying modular decomposition to parameterized cluster editing problems

DOI10.1007/s00224-007-9032-7zbMath1179.68111OpenAlexW2012224668MaRDI QIDQ2272201

Fábio Protti, Maise Dantas da Silva, Jayme Luiz Szwarcfiter

Publication date: 6 August 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9032-7

zbMATH Keywords

NP-complete problemsfixed-parameter tractabilitycluster graphsedge modification problemsbicluster graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (34)

Simpler Linear-Time Kernelization for Planar Dominating Set ⋮ Parameterizing edge modification problems above lower bounds ⋮ On Making Directed Graphs Transitive ⋮ Graph-Based Data Clustering with Overlaps ⋮ Cluster Editing ⋮ New heuristics for the bicluster editing problem ⋮ Orthology relations, symbolic ultrametrics, and cographs ⋮ On making directed graphs transitive ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Graph-based data clustering with overlaps ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ Branch-and-cut approaches for \(p\)-cluster editing ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Incremental problems in the parameterized complexity setting ⋮ Complexity and parameterized algorithms for cograph editing ⋮ Branch-and-price for \(p\)-cluster editing ⋮ A Problem Kernelization for Graph Packing ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ On the relation of strong triadic closure and cluster deletion ⋮ The biclique partitioning polytope ⋮ Efficient algorithms for cluster editing ⋮ Complexity of modification problems for reciprocal best match graphs ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Alternative Parameterizations for Cluster Editing ⋮ A parallel hybrid metaheuristic for bicluster editing ⋮ A fast branching algorithm for cluster vertex deletion ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph-modeled data clustering: Exact algorithms for clique generation
• Matrix multiplication via arithmetic progressions
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Applying Modular Decomposition to Parameterized Bicluster Editing
• A More Effective Linear Kernelization for Cluster Editing
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Algorithm Theory - SWAT 2004
• Transitiv orientierbare Graphen
• SOFSEM 2005: Theory and Practice of Computer Science
• Graph-Theoretic Concepts in Computer Science
• Complexity classification of some edge modification problems

This page was built for publication: Applying modular decomposition to parameterized cluster editing problems