Graph clustering problems under the Lens of parameterized local search

DOI10.4230/LIPICS.IPEC.2023.20MaRDI QIDQ6926189zbMATH OpenFDO

Authors Jaroslav Garvardt, Nils Morawietz, André Nichterlein, Mathias Weller

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.20

zbMATH Keywords

FPTW[1-hardness]parameterized local searchpermissive local search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 7803591 (Why is no real title available?)
• scientific article; zbMATH DE number 7803609 (Why is no real title available?)
• scientific article; zbMATH DE number 7803610 (Why is no real title available?)
• scientific article; zbMATH DE number 7803612 (Why is no real title available?)
• A 2k kernel for the cluster editing problem
• A golden ratio parameterized algorithm for cluster editing
• A more effective linear kernelization for cluster editing
• A tight approximation algorithm for the cluster vertex deletion problem
• Cluster deletion revisited
• Cluster editing with locally bounded modifications
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Combining clickstream analyses and graph-modeled data clustering for identifying common response processes
• Correlation clustering
• Efficient Parameterized Preprocessing for Cluster Editing
• Enumerating connected induced subgraphs: improved delay and experimental comparison
• Faster parameterized algorithm for cluster vertex deletion
• Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
• Fundamentals of parameterized complexity
• Graph clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• Improved bounds on Bell numbers and on moments of sums of random variables
• Incremental list coloring of graphs, parameterized by conservation
• Local search for string problems: brute-force is essentially optimal
• Local search: is brute-force avoidable?
• Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
• On the complexity of parameterized local search for the maximum parsimony problem
• On the parameterized complexity of consensus clustering
• On the relation of strong triadic closure and cluster deletion
• PACE Solver Description: µSolver - Heuristic Track *
• Parameterized algorithms
• Parameterized dynamic cluster editing
• Parameterized local search for vertex cover: when only the search radius is crucial
• Parameterizing edge modification problems above lower bounds
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Structural parameterization of cluster deletion
• The PACE 2021 parameterized algorithms and computational experiments challenge: cluster editing
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• The parameterized complexity of local search for TSP, more refined
• Turbocharging treewidth heuristics

Cited in

(2)

• When can cluster deletion with bounded weights be solved efficiently?
• When can cluster deletion with bounded weights be solved efficiently?

This page was built for publication: Graph clustering problems under the Lens of parameterized local search

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