Finding Connected Dense $$k$$-Subgraphs
From MaRDI portal
Publication:2948471
DOI10.1007/978-3-319-17142-5_22zbMath1459.68155arXiv1501.07348OpenAlexW1594283629MaRDI QIDQ2948471
Changjun Wang, Xiao-Dong Hu, Xu-jin 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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Density (toughness, etc.) (05C42)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
- Clustering and domination in perfect graphs
- Approximation algorithms for maximum dispersion
- An improved rounding method and semidefinite programming relaxation for graph partition
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Detecting high log-densities
- Graph expansion and the unique games conjecture
- Finding Connected Dense $$k$$-Subgraphs
- Densest k-Subgraph Approximation on Intersection Graphs
- Relations between average case complexity and approximation complexity
- Finding Dense Subgraphs with Size Bounds
- On Finding Dense Subgraphs
- Greedily Finding a Dense Subgraph
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The dense \(k\)-subgraph problem
