Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

DOI10.4230/LIPIcs.MFCS.2017.6zbMath1441.68105arXiv1706.09487OpenAlexW2962698119MaRDI QIDQ5111220

Nikolai Karpov, Ivan A. Bliznets

Publication date: 26 May 2020

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

zbMATH Keywords

clusteringparameterized complexityhighly connected clusters

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Editing graphs into disjoint unions of dense clusters
• Simple upper bounds for partition functions
• A clustering algorithm based on graph connectivity
• On the maximum quasi-clique problem
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• On clique relaxation models in network analysis
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Fourier meets M\"{o}bius: fast subset convolution
• Finding Highly Connected Subgraphs
• A Graph-Theoretic Approach to a Communications Problem

This page was built for publication: Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters