Two heuristics for the rainbow spanning forest problem

Sudishna Ghoshal and Shyam Sundar

European Journal of Operational Research, 2020, vol. 285, issue 3, 853-864

Abstract: A rainbow spanning forest (say RF) of a given connected, undirected and edge-colored graph (G) is a spanning forest of a set of rainbow components, where a rainbow component is a tree whose edges have different colors. The rainbow spanning forest problem (RSFP) of G aims to find a RF of G with the minimum number of rainbow components. The RSFP which is recently introduced is NP-hard on general graphs and trees, but finds its applications in many situations in which one requires to distinguish between different types of connections in network. To the best of our knowledge, there exists only one paper (Carrabs et al. 2018b) that presents a problem-specific heuristic called greedy algorithm (say GH) and a multi-start scheme embedding this GH (say MSGH) in order to further improve the results. This paper presents a novel and fast problem-specific heuristic Heu_RSF. With the intent of improving solution quality at the cost of higher computational time, we present an artificial bee colony algorithm (ABC_RSFP) for the RSFP. Main components of ABC_RSFP such as randomized version of Heu_RSF in solution initialization and grouping-based neighborhood strategies in conjunction with the use of Heu_RSF as a repair operator help in making ABC_RSFP more effective framework. On a set of benchmark instance scenarios, experimental results suggest that Heu_RSF is effective particularly on instances of larger scenarios with higher density and is computationally much faster than GH and MSGH. ABC_RSFP outperforms MSGH on almost all instance scenarios and shows its effectiveness in terms of computational time.

Keywords: (O) Combinatorial optimization; Rainbow spanning forest problem; Problem-specific heuristic; Artificial bee colony algorithm; Neighborhood strategies (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720301831
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:285:y:2020:i:3:p:853-864

DOI: 10.1016/j.ejor.2020.02.045

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().