Brunel University Research Archive(BURA) preserves and enables easy and open access to all
types of digital content. It showcases Brunel's research outputs.
Research contained within BURA is open access, although some publications may be subject
to publisher imposed embargoes. All awarded PhD theses are also archived on BURA.
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 | Size | Format | |
|---|---|---|---|---|
| modularitybura.pdf | 112.71 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.