Brunel University Research Archive (BURA) >
University >
Publications >

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
Publication 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:Mathematical Science
Computer Science
Dept of Mathematics Research Papers

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.