Asymptotic bounds for clustering problems in random graphs

DOI10.1002/net.22203OpenAlexW4389742209MaRDI QIDQ6196888

Sergiy I. Butenko, Pavlo A. Krokhmal, Eugene Lykhovyd

Publication date: 15 March 2024

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.22203

zbMATH Keywords

network analysisasymptotic boundsindependent union of cliquesuniform random graphsnetwork clusterability

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• A \(2k\) kernel for the cluster editing problem
• Fixed-parameter algorithms for cluster vertex deletion
• Cluster analysis and mathematical programming
• Dense subgraphs in random graphs
• On the maximum quasi-clique problem
• The nature of computation. Logic, algorithms, applications. 9th conference on computability in Europe, CiE 2013, Milan, Italy, July 1--5, 2013. Proceedings
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• The maximum number of induced open triangles in graphs of a given order
• Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs
• The maximum independent union of cliques problem: complexity and exact approaches
• On clique relaxation models in network analysis
• Exact algorithms for the minimum \(s\)-club partitioning problem
• Network analysis. Methodological foundations.
• Distance-Based Clique Relaxations in Networks: s-Clique and s-Club
• On the 2-Club Polytope of Graphs
• Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
• Emergence of Scaling in Random Networks
• Cliques in random graphs
• A graph‐theoretic generalization of the clique concept
• Turan's Graph Theorem
• Graph Partitioning and Graph Clustering
• Node-and edge-deletion NP-complete problems

This page was built for publication: Asymptotic bounds for clustering problems in random graphs