• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Greedy Randomized Adaptive Search Procedure for the maximum co-k-plex problem.
【24h】

Greedy Randomized Adaptive Search Procedure for the maximum co-k-plex problem.

机译：最大co-k-plex问题的贪婪随机自适应搜索过程。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The focus of this thesis is a degree based relaxation of independent sets in graphs called co-k-plexes and the related combinatorial optimization problem of finding a maximum cardinality co-k-plex in. This thesis develops a metaheuristic approach for solving the maximum co-k-plex problem which is known to be NP-hard. The approach is further extended for finding a maximum weighted co-k-plex in where vertices of are associated with specific weights. As the maximum co-k-plex problem in is equivalent to the maximum k-plex problem in G¯, many applications of this problem can be found in clustering and data mining social networks, biological networks, internet graphs and stock market graphs among others.;In this thesis, a Greedy Randomized Adaptive Search Procedure (GRASP) is developed to solve the maximum co-k-plex and maximum weighted co-k-plex problems. Computational experiments are performed to study the effectiveness of the proposed metaheuristic on benchmark instances. Finally, the performance of the developed GRASP algorithms for both versions was confirmed by comparing the running time and solution quality with results obtained by an exact algorithm.
机译：本文的重点是基于度的图上独立集的松弛，称为co-k-plex，以及在其中找到最大基数的k-plex的相关组合优化问题。本文提出了一种求解最大co-k-plex的元启发式方法。 -k-plex问题，已知为NP-困难。该方法被进一步扩展以找到最大加权的co-k-plex，其中的顶点与特定权重相关联。由于最大的co-k-plex问题等于G′中的最大k-plex问题，因此该问题的许多应用可以在聚类和数据挖掘社交网络，生物网络，互联网图和股票市场图等中找到。本文提出了一种贪婪随机自适应搜索程序（GRASP）来解决最大co-k-plex和最大加权co-k-plex问题。进行计算实验以研究所提出的元启发式方法在基准实例上的有效性。最后，通过将运行时间和解决方案质量与通过精确算法获得的结果进行比较，证实了针对两种版本开发的GRASP算法的性能。

著录项

  • 作者

    Bhave, Amol Atmaram.;

  • 作者单位

    Oklahoma State University.;

  • 授予单位 Oklahoma State University.;
  • 学科 Mathematics.;Operations Research.;Engineering Industrial.
  • 学位 M.S.
  • 年度 2010
  • 页码 67 p.
  • 总页数 67
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号