Maximizing edge-ratio is NP-complete

Noble S.D.; Hansen P.; Mladenovi? N.

首页> 外文期刊>Discrete Applied Mathematics >Maximizing edge-ratio is NP-complete

【24h】

Maximizing edge-ratio is NP-complete

机译：最大化边缘比率是NP完全的

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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.

机译：给定一个图G及其顶点的二分法，这两个类别的边沿比率是最小值，因此定义为其内部边数除以切边数。我们证明最大化边缘比率是NP完全的。

著录项

来源
《Discrete Applied Mathematics》 |2011年第18期|共5页
作者
Noble S.D.; Hansen P.; Mladenovi? N.;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
Community detection; Edge-ratio; Graph clustering; NP-complete;

机译：社区检测边缘比率图聚类NP完全;

相似文献

外文文献
中文文献
专利

1. Maximizing edge-ratio is NP-complete [J] . Noble S.D., Hansen P., Mladenovi? N. Discrete Applied Mathematics . 2011,第18期

机译：最大化边缘比率是NP完全的
2. Edge-ratio network clustering by Variable Neighborhood Search [J] . Sonia Cafieri, Pierre Hansen, Nenad Mladenovi? The European physical journal, B. Condensed matter physics . 2014,第5期

机译：可变邻域搜索的边缘比率网络聚类
3. Medical diagnosis and treatment is NP-complete [J] . Arle Jeffrey. E., Carlson Kristen W. Journal of Experimental and Theoretical Artificial Intelligence . 2021,第2期

机译：医学诊断和治疗是NP-Complete
4. Deciding Non-emptiness of Hypergraph Languages Generated by Connection-preserving Fusion Grammars is NP-complete [C] . Aaron Lye International Conference on Language and Automata Theory and Applications . 2021

机译：决定连接保存融合语法生成的超空白的非空虚是NP-Complete
5. Exploring Approximation Algorithms and Their Empirical Analysis For Selected NP-Complete Problems. [D] . Doss, Roger G. 2011

机译：探索所选NP完全问题的近似算法及其经验分析。
6. Correction to ‘Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems’ [O] . Falco C. M. J. M. van Delft, Giulia Ipolitti, Dan V. Nicolau Jr, 2019

机译：更正了必须提供的东西：通过生物代理探索编码NP完全问题的物理网络来扩展组合计算
7. Maximizing edge-ratio is NP-complete [O] . Steven D. Noble, Pierre Hansen, Nenad Mladenović 2012

机译：最大化边缘比率是NP完全的

Maximizing edge-ratio is NP-complete

摘要

著录项

相似文献

相关主题

期刊订阅