Maximizing edge-ratio is NP-complete

DC Field	Value	Language
dc.contributor.author	Noble, Steven	en
dc.contributor.author	Hansen, Pierre	en
dc.contributor.author	Mladenović, Nenad	en
dc.date.accessioned	2020-05-02T16:42:06Z	-
dc.date.available	2020-05-02T16:42:06Z	-
dc.date.issued	2011-12-06	en
dc.identifier.issn	0166-218X	en
dc.identifier.uri	http://researchrepository.mi.sanu.ac.rs/handle/123456789/2494	-
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
dc.publisher	Elsevier	-
dc.relation.ispartof	Discrete Applied Mathematics	en
dc.subject	Community detection \| Edge-ratio \| Graph clustering \| NP-complete	en
dc.title	Maximizing edge-ratio is NP-complete	en
dc.type	Article	en
dc.identifier.doi	10.1016/j.dam.2011.07.016	en
dc.identifier.scopus	2-s2.0-82955247950	en
dc.relation.firstpage	2276	en
dc.relation.lastpage	2280	en
dc.relation.issue	18	en
dc.relation.volume	159	en
dc.description.rank	M22	-
item.cerifentitytype	Publications	-
item.openairecristype	http://purl.org/coar/resource_type/c_18cf	-
item.openairetype	Article	-
item.grantfulltext	none	-
item.fulltext	No Fulltext	-
crisitem.author.orcid	0000-0001-6655-0409	-

2

checked on Jun 1, 2024

58

checked on May 9, 2024

Check