| Authors: | Noble, Steven Hansen, Pierre Mladenović, Nenad |
Title: | Maximizing edge-ratio is NP-complete | Journal: | Discrete Applied Mathematics | Volume: | 159 | Issue: | 18 | First page: | 2276 | Last page: | 2280 | Issue Date: | 6-Dec-2011 | Rank: | M22 | ISSN: | 0166-218X | DOI: | 10.1016/j.dam.2011.07.016 | Abstract: | Given a graph G and a bipartition of its vertices, the edge-ratio is the minimum for both classes so defined of their number of internal edges divided by their number of cut edges. We prove that maximizing edge-ratio is NP-complete. |
Keywords: | Community detection | Edge-ratio | Graph clustering | NP-complete | Publisher: | Elsevier |
Show full item record
SCOPUSTM
Citations
2
checked on Nov 19, 2024
Page view(s)
15
checked on Nov 19, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.