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/6309Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Noble, SD | - |
| dc.contributor.author | Hansen, P | - |
| dc.contributor.author | Mladenović, N | - |
| dc.date.accessioned | 2012-03-19T09:37:15Z | - |
| dc.date.available | 2012-03-19T09:37:15Z | - |
| dc.date.issued | 2011 | - |
| dc.identifier.citation | Discrete Applied Mathematics, 159(18): 2276 - 2280, Dec 2011 | en_US |
| dc.identifier.issn | 0166-218X | - |
| dc.identifier.uri | http://www.sciencedirect.com/science/article/pii/S0166218X11002770 | en |
| dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/6309 | - |
| dc.description | This is the post-print verison of the Article. The official published version can be accessed from the link below - Copyright @ 2011 Elsevier | en_US |
| dc.description.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. | en_US |
| dc.language.iso | en | en_US |
| dc.publisher | Elsevier | en_US |
| dc.subject | Graph clustering | en_US |
| dc.subject | Community detection | en_US |
| dc.subject | Edge-ratio | en_US |
| dc.subject | NP-complete | en_US |
| dc.title | Maximizing edge-ratio is NP-complete | en_US |
| dc.type | Article | en_US |
| dc.identifier.doi | http://dx.doi.org/10.1016/j.dam.2011.07.016 | - |
| pubs.organisational-data | /Brunel | - |
| pubs.organisational-data | /Brunel/Brunel Active Staff | - |
| pubs.organisational-data | /Brunel/Brunel Active Staff/School of Info. Systems, Comp & Maths | - |
| pubs.organisational-data | /Brunel/Brunel Active Staff/School of Info. Systems, Comp & Maths/Maths | - |
| 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.