Finding connected \(k\)-subgraphs with high density

DOI10.1016/j.ic.2017.07.003zbMath1376.05145OpenAlexW2735921087MaRDI QIDQ2407097

Changjun Wang, Xiao-Dong Hu, Xu-jin Chen

Publication date: 28 September 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.07.003

zbMATH Keywords

connectivityapproximation algorithmsinterval graphsdensest \(k\)-subgraphsheaviest \(k\)-subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22) Density (toughness, etc.) (05C42)

Related Items

Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic graphs, Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph, Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph, On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• The densest \(k\)-subgraph problem on clique graphs
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Detecting high log-densities
• Graph expansion and the unique games conjecture
• Efficient Optimization of Monotonic Functions on Trees
• 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
• Heuristic and Special Case Algorithms for Dispersion Problems
• Greedily Finding a Dense Subgraph
• PTAS for Densest k-Subgraph in Interval Graphs
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem