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

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/6309

Title: Maximizing edge-ratio is NP-complete
Authors: Noble, SD
Hansen, P
Mladenović, N
Keywords: Graph clustering
Community detection
Edge-ratio
NP-complete
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
URI: http://www.sciencedirect.com/science/article/pii/S0166218X11002770
http://bura.brunel.ac.uk/handle/2438/6309
DOI: http://dx.doi.org/10.1016/j.dam.2011.07.016
ISSN: 0166-218X
Appears in Collections:Mathematics
Information Systems and Computing
School of Information Systems, Computing and Mathematics Research Papers
Publications

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.

 


Library (c) Brunel University.    Powered By: DSpace
Send us your
Feedback. Last Updated: September 14, 2010.
Managed by:
Hassan Bhuiyan