Applying modular decomposition to parameterized cluster editing problems
DOI10.1007/S00224-007-9032-7zbMATH Open1179.68111OpenAlexW2012224668MaRDI QIDQ2272201FDOQ2272201
Fábio Protti, Maise Dantas da Silva, Jayme L. 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
Recommendations
fixed-parameter tractabilityNP-complete problemscluster graphsedge modification problemsbicluster graphs
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)
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Automated generation of search tree algorithms for hard graphs modification problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Matrix multiplication via arithmetic progressions
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Transitiv orientierbare Graphen
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Complexity classification of some edge modification problems
- Applying Modular Decomposition to Parameterized Bicluster Editing
- Graph-Theoretic Concepts in Computer Science
- Cluster graph modification problems
- A More Effective Linear Kernelization for Cluster Editing
- A general method to speed up fixed-parameter-tractable algorithms
- A Fast Algorithm for the Decomposition of Graphs and Posets
- Graph-modeled data clustering: Exact algorithms for clique generation
- Algorithm Theory - SWAT 2004
- SOFSEM 2005: Theory and Practice of Computer Science
- Efficient and practical algorithms for sequential modular decomposition
- Title not available (Why is that?)
Cited In (37)
- A fast branching algorithm for cluster vertex deletion
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- Efficient algorithms for cluster editing
- Cluster Editing
- On Making Directed Graphs Transitive
- Cograph editing: Merging modules is equivalent to editing P_4s
- Graph-Based Data Clustering with Overlaps
- On making directed graphs transitive
- Parameterizing edge modification problems above lower bounds
- Graph-based data clustering with overlaps
- On the relation of strong triadic closure and cluster deletion
- Fixed-parameter algorithms for cluster vertex deletion
- Applying Modular Decomposition to Parameterized Bicluster Editing
- Improved Algorithms for Bicluster Editing
- Simpler Linear-Time Kernelization for Planar Dominating Set
- Branch-and-price for \(p\)-cluster editing
- A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
- The Multi-parameterized Cluster Editing Problem
- A cubic-vertex kernel for flip consensus tree
- The biclique partitioning polytope
- A parallel hybrid metaheuristic for bicluster editing
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- A survey of the algorithmic aspects of modular decomposition
- Orthology relations, symbolic ultrametrics, and cographs
- Complexity of modification problems for reciprocal best match graphs
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- Towards optimal and expressive kernelization for \(d\)-hitting set
- A faster algorithm for the cluster editing problem on proper interval graphs
- New heuristics for the bicluster editing problem
- Alternative Parameterizations for Cluster Editing
- A Problem Kernelization for Graph Packing
- Branch-and-cut approaches for \(p\)-cluster editing
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Fixed-parameter algorithms for DAG partitioning
- Complexity and parameterized algorithms for cograph editing
- Incremental problems in the parameterized complexity setting
This page was built for publication: Applying modular decomposition to parameterized cluster editing problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272201)
