Finding Connected Dense k-Subgraphs

DOI10.1007/978-3-319-17142-5_22MaRDI QIDQ2948471zbMATH OpenOpenAlexFDO

Authors Xiaodong Hu, Changjun Wang, Xujin Chen

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

connectivitycombinatorial approximation algorithmsdensest \(k\)-subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40) Density (toughness, etc.) (05C42)

Abstract: Given a connected graph $G$ on $n$ vertices and a positive integer $klen$, a subgraph of $G$ on $k$ vertices is called a $k$-subgraph in $G$. We design combinatorial approximation algorithms for finding a connected $k$-subgraph in $G$ such that its density is at least a factor $Omega(max{n}^{-2/5},k^2/n^2)$ of the density of the densest $k$-subgraph in $G$ (which is not necessarily connected). These particularly provide the first non-trivial approximations for the densest connected $k$-subgraph problem on general graphs.

Recommendations

• Finding densest \(k\)-connected subgraphs
• Finding connected \(k\)-subgraphs with high density
• On Finding Dense Subgraphs
• Finding dense subgraphs
• Finding dense subgraphs of sparse graphs
• Finding Dense Subgraphs with Size Bounds
• The dense \(k\)-subgraph problem
• Computing the \(k\) densest subgraphs of a graph
• Finding dense subgraphs in \(G(n,1/2)\)
• In search of the densest subgraph

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1182772 (Why is no real title available?)
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• An improved rounding method and semidefinite programming relaxation for graph partition
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation algorithms for maximum dispersion
• Clustering and domination in perfect graphs
• Densest k-subgraph approximation on intersection graphs
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Finding Connected Dense k-Subgraphs
• Finding Dense Subgraphs with Size Bounds
• Graph expansion and the unique games conjecture
• Greedily Finding a Dense Subgraph
• On Finding Dense Subgraphs
• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem

Cited in

(8)

• LATIN 2004: Theoretical Informatics
• Finding connected \(k\)-subgraphs with high density
• Computing connected-k-subgraph cover with connectivity requirement
• Finding Connected Dense k-Subgraphs
• A decomposition of a graph into dense subgraphs
• Can we locally compute sparse connected subgraphs?
• A graph theoretical analysis of the number of edges in \(k\)-dense graphs
• Finding densest \(k\)-connected subgraphs

This page was built for publication: Finding Connected Dense $$k$$-Subgraphs

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