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
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
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: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.