Please use this identifier to cite or link to this item:
Title: Maximizing edge-ratio is NP-complete
Authors: Noble, SD
Hansen, P
Mladenović, N
Keywords: Graph clustering;Community detection;Edge-ratio;NP-complete
Issue Date: 2011
Publisher: Elsevier
Citation: Discrete Applied Mathematics, 159(18): 2276 - 2280, Dec 2011
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.
Description: This is the post-print verison of the Article. The official published version can be accessed from the link below - Copyright @ 2011 Elsevier
ISSN: 0166-218X
Appears in Collections:Publications
Computer Science
Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
modularitybura.pdf112.71 kBAdobe PDFView/Open

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