On the complexity of multi-parameterized cluster editing

DOI10.1016/j.jda.2017.07.003zbMath1419.68056arXiv1511.09360OpenAlexW2963069757MaRDI QIDQ2407948

Faisal N. Abu-Khzam

Publication date: 6 October 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.09360

zbMATH Keywords

cluster editingfixed-parameter tractabilitykernelizationmulti-parameterization

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) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion ⋮ \((1,1)\)-cluster editing is polynomial-time solvable ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Parameterized dynamic cluster editing ⋮ Parallel Algorithm for Enumerating Maximal Cliques in Complex Network ⋮ Parameterized Dynamic Cluster Editing

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• A \(2k\) kernel for the cluster editing problem
• Exact algorithms for cluster editing: Evaluation and experiments
• Cluster editing with locally bounded modifications
• Graph-modeled data clustering: Exact algorithms for clique generation
• Sufficient conditions for edit-optimal clusters
• Fixed-parameter enumerability of cluster editing and related problems
• A more effective linear kernelization for cluster editing
• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
• Going weighted: parameterized algorithms for cluster editing
• NP-hard problems in hierarchical-tree clustering
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• A golden ratio parameterized algorithm for cluster editing
• Clustering with local restrictions
• Parametrized complexity theory.
• The Multi-parameterized Cluster Editing Problem
• Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• Parameterized Algorithms

This page was built for publication: On the complexity of multi-parameterized cluster editing