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 Dec 2, 2021

Page view(s)

12
checked on Dec 3, 2021

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.