Path relinking for the vertex separator problem

作者：

Highlights：

• We present a path relinking algorithm for the NP-hard vertex separator problem in graphs.

• We use two complementary search operators in iterated tabu search.

• We show computational results and comparisons on 365 benchmark graphs.

• We report 67 improved best results (new upper bounds).

摘要

•We present a path relinking algorithm for the NP-hard vertex separator problem in graphs.•We use two complementary search operators in iterated tabu search.•We show computational results and comparisons on 365 benchmark graphs.•We report 67 improved best results (new upper bounds).

论文关键词：Vertex separator,Graph partitioning,Path relinking,Population-based heuristics

论文评审过程：Received 21 February 2017, Revised 28 March 2017, Accepted 29 March 2017, Available online 31 March 2017, Version of Record 19 April 2017.

论文官网地址：https://doi.org/10.1016/j.eswa.2017.03.064