Семинар за рачунарство и примењену математику, 1. март 2016.

• 29. Фебруар, 2016
• Коментари (0)

Наредни састанак Семинара биће одржан у уторак, 1. марта 2016. у сали 301ф Математичког института САНУ са почетком у 14:15 часова.

Предавач: Зорица Дражић, Математички факултет, Универзитет у Београду

Наслов предавања: A METAHEURISTIC APPROACH TO THE DOMINATING TREE PROBLEM

Апстракт: This paper considers a recently introduced NP-hard problem on graphs, called the dominating tree problem (DTP). In order to solve this problem, we develop a variable neighborhood search (VNS) based heuristic. Feasible solutions are obtained by using the set of vertex permutations that allow us to implement standard neighborhood structures and the appropriate local search procedure. Computational experiments include two classes of randomly generated test instances and benchmark test instances from the literature. Optimality of VNS solutions on small size instances is verified with CPLEX.