G-2011-32
Maximizing Edge-Ratio Is NP-Complete
, et référence BibTeX
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.
Paru en juin 2011 , 12 pages
Axe de recherche
Applications de recherche
Publication
jan. 2011
Maximizing edge-ratio is NP-complete
, et
Discrete Applied Mathematics, 159(18), 2276–2280, 2011
référence BibTeX