Naslov
A Genetic Algorithm for Group Steiner Tree Problem

Autori
Čorić, Rebeka ; Đumić, Mateja ; Jelić, Slobodan

Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni

Izvornik
MIPRO 2018 41st International Convention Proceedings / Karolj, Skala - Rijeka : Hrvatska udruga za informacijsku i komunikacijsku tehnologiju, elektroniku i mikroelektroniku - MIPRO, 2018, 1113-1118

ISBN
978-953-233-096-0

Skup
41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO 2018)

Mjesto i datum
Opatija, Hrvatska, 21.05.2018. - 25.05.2018

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
genetic algorithm, group Steiner tree problem, minimum spanning tree, integer linear programming

Sažetak
In Group Steiner Tree Problem (GST) we are given a weighted undirected graph and family of subsets of vertices which are called groups. Our objective is to find a minimum-weight subgraph which contains at least one vertex from each group (groups do not have to be disjoint). GST is NP-hard combinatorial optimization problem that arises from many complex real-life problems such as finding substrate-reaction pathways in protein networks, progressive keyword search in relational databases, team formation in social networks, etc. Heuristic methods are extremely important for finding the good-enough solutions in short time. In this paper we present genetic algorithm for solving GST. We also give results of computational experiments with comparisons to optimal solutions.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA