Efficient approaches for the Flooding Problem on graphs

André Renato Villela Silva (), Luiz Satoru Ochi (), Bruno José da Silva Barros () and Rian Gabriel S. Pinheiro ()
Additional contact information
André Renato Villela Silva: Universidade Federal Fluminense - Instituto de Ciência e Tecnologia
Luiz Satoru Ochi: Universidade Federal Fluminense - Instituto de Computação
Bruno José da Silva Barros: Universidade Federal Rural de Pernambuco - Unidade Acadêmica de Garanhuns
Rian Gabriel S. Pinheiro: Universidade Federal Rural de Pernambuco - Unidade Acadêmica de Garanhuns

Annals of Operations Research, 2020, vol. 286, issue 1, No 3, 33-54

Abstract: Abstract This paper deals with the Flooding Problem on graphs. This problem consists in finding the shortest sequence of flooding moves that turns a colored graph into a monochromatic one. The problem has applications in some areas as disease propagation, for example. Three metaheuristics versions are proposed and compared with the literature results. A new integer programming formulation is also proposed and tested with the only formulation known. The obtained results indicate that both the proposed formulation and the Evolutionary Algorithm are, respectively, the best exact and heuristic approaches for the problem.

Keywords: Evolutionary Algorithms; GRASP; Iterated local search; Metaheuristics; Mixed integer problem; Flooding Problem (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2796-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:286:y:2020:i:1:d:10.1007_s10479-018-2796-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2796-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().