Path relinking for the vertex separator problem

doi:10.1016/j.eswa.2017.03.064

2017-10-01

PRE

Yang Wang

Jin‐Kao Hao *

DOI：10.1016/j.eswa.2017.03.064

原文链接

原文求助

摘要

En 中文

本文提出了第一个基于种群的路径重连算法，用于解决图中的NP-硬顶点分隔符问题。所提出的算法采用专用的重新链接过程来生成初始解决方案和从精英解决方案 (总体) 的参考集获取的指导解决方案之间的中间解决方案，并使用快速禁忌搜索过程来改进某些选定的中间解决方案。特别注意确保参考集的多样性。采用基于桶排序的专用数据结构来确保高计算效率。所提出的算法在具有多达20,000个顶点的四组365基准实例上进行了评估，并且与文献中的最新方法相比，显示出高度可比较的结果。具体来说，我们报告了67个实例的改进的最佳解决方案 (新的上限)，这些实例可以作为评估该问题其他算法的参考值。（C）2017 Elsevier Ltd.版权所有。

Keyword:

Vertex separator

Graph partitioning

Path relinking

Population-based heuristics

AI总结

对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

Expert Systems with Applications

IF:

7.5

论文数:

3.0W

被引数:

10.2W

机构

Northwestern Polytechnical University

学者数:

4.6W

论文数: 3.7W

被引数: 5.3W

引用论文

Applying the Happenstance Learning Theory to Involuntary Career Transitions

The Career Development Quarterly

IF0

2013-02-28

OAAI

John D. Krumboltz; Pamela F. Foley; Elizabeth W. Cotter

Continuous quadratic programming formulations of optimization problems on graphs 图上优化问题的连续二次规划公式

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

IF6

2015-01-01

PREAI

Hager, William W.; Hungerford, James T.

The use of safety or uncertainty factors in the setting of acute reference doses

Food Additives and Contaminants

IF0

2000-07-01

PREAI

A. G. Renwick

Total Ionizing Dose Effects in 3-D NAND Flash Memories

IEEE Transactions on Nuclear Science

IF0

2019-01-01

PREAI

Marta Bagatin; Simone Gerardin; Alessandro Paccagnella; Silvia Beltrami; Alessandra Costantino; Michele Muschitiello; Ali Zadeh; Veronique Ferlet-Cavrois

Detección de ooquistes de Cryptosporidium parvum (Apicomplexa: Cryptosporidiidae) en ejemplares de cholga Aulacomya ater, extraídas desde la costa de la Región del Bío Bío, Chile

Revista chilena de infectología

IF0

2020-06-01