Maximizing edge-ratio is NP-complete

DOI10.1016/j.dam.2011.07.016zbMath1408.68069OpenAlexW2055422348MaRDI QIDQ765326

Steven D. Noble, Nenad Mladenović, Pierre Hansen

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.07.016

zbMATH Keywords

NP-completenesscommunity detectiongraph clusteringedge-ratio

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

A general view on computing communities

Cites Work

• Some simplified NP-complete graph problems
• On clusterings
• Unnamed Item