Two novel branch and bound algorithms for the vertex bisection problem

作者：

Highlights：

• Two representations of the search tree for the branch and bound algorithm.

• Two new greedy constructive heuristics for the vertex bisection problem.

• A new lower bound computation for the vertex bisection problem.

• New optimal solutions for four Harwell–Boing instances.

摘要

•Two representations of the search tree for the branch and bound algorithm.•Two new greedy constructive heuristics for the vertex bisection problem.•A new lower bound computation for the vertex bisection problem.•New optimal solutions for four Harwell–Boing instances.

论文关键词：Vertex bisection problem,B&B,Upper bound,Lower bound,Constructive heuristic

论文评审过程：Received 11 March 2020, Revised 23 October 2021, Accepted 27 October 2021, Available online 16 November 2021, Version of Record 19 November 2021.

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