Parameterized Dynamic Cluster Editing

DOI10.4230/LIPICS.FSTTCS.2018.46MaRDI QIDQ5090987OpenAlexFDO

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

Publication date 21 July 2022

Full work available at URL https://depositonce.tu-berlin.de/bitstream/11303/12837/1/Luo_etal_Parameterized_2021.pdf

zbMATH Keywords

fixed-parameter tractabilityNP-hard problemsparameterized hardnesscompromise clusteringgoal-oriented clusteringgraph-based data clustering

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Parameterized dynamic cluster editing
• Alternative parameterizations for cluster editing
• Efficient Parameterized Preprocessing for Cluster Editing
• Cluster editing
• The Multi-parameterized Cluster Editing Problem
• Cluster editing with locally bounded modifications
• On the complexity of multi-parameterized cluster editing
• Fixed-Parameter Tractable Generalizations of Cluster Editing
• Even faster parameterized cluster deletion and cluster editing
• Efficient algorithms for cluster editing

Cites work

• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• A theory and algorithms for combinatorial reoptimization
• Cluster editing
• Cluster editing with locally bounded modifications
• Cluster editing with vertex splitting
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Clustering With Multi-Layer Graphs: A Spectral Perspective
• Correlation clustering
• Dynamic dominating set and turbo-charging greedy heuristics
• Dynamic parameterized problems
• Graph-modeled data clustering: Exact algorithms for clique generation
• Incremental Clustering and Dynamic Information Retrieval
• Incremental list coloring of graphs, parameterized by conservation
• Local equivalences of distances between clusterings -- a geometric perspective
• Local search: is brute-force avoidable?
• On the Hardness of Reoptimization
• On the complexity of multi-parameterized cluster editing
• On the parameterized complexity of dynamic problems
• Parameterized algorithms
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Temporal clustering
• The parameterized complexity of local search for TSP, more refined
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis

Cited in

(2)

• Cluster editing with vertex splitting
• Parameterized dynamic cluster editing

This page was built for publication: Parameterized Dynamic Cluster Editing

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