|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
checked on Dec 2, 2021
checked on Dec 3, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.