Scholarlink

In this paper, we present a Branch & Bound algorithm for solving an NP-hard combinatorial optimisation problem denoted as Rainbow Spanning Forest Problem (RSFP). The RSFP consists of finding a spanning forest of an undirected, edge-coloured graph G with the minimum number of rainbow components, where a rainbow component of G is a subgraph of G that has all the edges with different colours. The proposed method is capable of determining the optimal solution within 0.4 s for small instances, thus proving to be computationally competitive with respect to the methods used by the most recent optimisation libraries and commercial SW environments available.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Branch & Bound Algorithm for the Rainbow Spanning Forest Problem

  • 章节

  • 发表日期：

    2026年

查看全文
  • Carmine Cerrone,
  • Raffaele Dragone,
  • Anna Sciomachen

摘要

In this paper, we present a Branch & Bound algorithm for solving an NP-hard combinatorial optimisation problem denoted as Rainbow Spanning Forest Problem (RSFP). The RSFP consists of finding a spanning forest of an undirected, edge-coloured graph G with the minimum number of rainbow components, where a rainbow component of G is a subgraph of G that has all the edges with different colours. The proposed method is capable of determining the optimal solution within 0.4 s for small instances, thus proving to be computationally competitive with respect to the methods used by the most recent optimisation libraries and commercial SW environments available.