Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters

DOI10.4230/LIPICS.MFCS.2017.6zbMATH Open1441.68105arXiv1706.09487OpenAlexW2962698119MaRDI QIDQ5111220FDOQ5111220

Authors: Nikolai Karpov, I. A. Bliznets 

Publication date: 26 May 2020

Abstract: Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model, clusters are generally defined as cliques. However, such an approach might be too restrictive as in some applications, not all objects from the same cluster must be connected. That is why different types of cliques relaxations often considered as clusters. In our work, we consider a problem of partitioning graph into clusters and a problem of isolating cluster of a special type whereby cluster we mean highly connected subgraph. Initially, such clusterization was proposed by Hartuv and Shamir. And their HCS clustering algorithm was extensively applied in practice. It was used to cluster cDNA fingerprints, to find complexes in protein-protein interaction data, to group protein sequences hierarchically into superfamily and family clusters, to find families of regulatory RNA structures. The HCS algorithm partitions graph in highly connected subgraphs. However, it is achieved by deletion of not necessarily the minimum number of edges. In our work, we try to minimize the number of edge deletions. We consider problems from the parameterized point of view where the main parameter is a number of allowed edge deletions.

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

Recommendations

• Parameterized algorithms for graph partitioning problems
• Parameterized algorithms for graph partitioning problems
• (Semi-)External Algorithms for Graph Partitioning and Clustering
• Optimal clustering of multipartite graphs
• Partitioning a graph into highly connected subgraphs
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• scientific article; zbMATH DE number 736961
• Publication:4941836

zbMATH Keywords

clusteringparameterized complexityhighly connected clusters

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• (Semi-)External Algorithms for Graph Partitioning and Clustering
• A survey of parameterized algorithms and the complexity of edge modification
• Moving clusters within a memetic algorithm for graph partitioning

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

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