Parameterized dynamic cluster editing

DOI10.1007/s00453-020-00746-yOpenAlexW3044843373MaRDI QIDQ2223691

Hendrik Molter, André Nichterlein, Rolf Niedermeier, Jun-Jie Luo

Publication date: 1 February 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

local searchfixed-parameter tractabilityparameterized complexitykernelizationcorrelation clusteringincremental clustering\textsf{NP}-hard problemscompromise clusteringgoal-oriented clusteringgraph-based data clusteringmulti-choice knapsack

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Multistage graph problems on a global budget ⋮ A new temporal interpretation of cluster editing ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The parameterized complexity of local search for TSP, more refined
• Fundamentals of parameterized complexity
• Incremental list coloring of graphs, parameterized by conservation
• A \(2k\) kernel for the cluster editing problem
• Local equivalences of distances between clusterings -- a geometric perspective
• Local search: is brute-force avoidable?
• Correlation clustering
• Cluster editing with locally bounded modifications
• Dynamic parameterized problems
• Graph-modeled data clustering: Exact algorithms for clique generation
• On the parameterized complexity of dynamic problems
• On the parameterized complexity of multiple-interval graph problems
• A more effective linear kernelization for cluster editing
• Cluster editing with vertex splitting
• A theory and algorithms for combinatorial reoptimization
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• On the complexity of multi-parameterized cluster editing
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Parametrized complexity theory.
• Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis
• Clustering With Multi-Layer Graphs: A Spectral Perspective
• Incremental Clustering and Dynamic Information Retrieval
• Reducibility among Combinatorial Problems
• Parameterized Dynamic Cluster Editing
• Cluster Editing in Multi-Layer and Temporal Graphs.
• Cluster Editing
• On the Hardness of Reoptimization
• Parameterized Algorithms

This page was built for publication: Parameterized dynamic cluster editing