Logowanie

Języki

  • Polski
  • English

Seminarium ZOK: Joachim Spoerhase o Approximation Algorithms for Degree-Based Spanning Tree Problems  

W dniu 12 lutego 2015 (czwartek, godz. 12:15-14:00, sala 119) na seminarium Zakładu Optymalizacji Kombinatorycznej Joachim Spoerhase przedstawi wyniki na temat Approximation Algorithms for Degree-Based Spanning Tree Problems.

Streszczenie

In this talk we consider discrete optimization problems of the following type. The input is an unweighted graph G. The goal is to find a spanning tree T of G that optimizes an objective function only depending on the distribution of node degrees in T. We will discuss constant factor approximation algorithms for three specific problems of this type, namely, the maximum leaf spanning tree problem, the maximum internal spanning tree problem and the minimum branch node spanning tree problem. The approximation algorithms are based on local search and greedy strategies.

Adres:
Instytut Informatyki
Uniwersytetu Wroclawskiego
ul. Joliot-Curie 15
50-383 Wroclaw
Sekretariat
tel.: 71 375 7800
tel.: 71 325 1271
fax: 71 375 7801
sekretariat@ii.uni.wroc.pl
Dziekanat
tel.: 71 375 7892
dziekan@ii.uni.wroc.pl
sprawy studenckie:
dziekanat@ii.uni.wroc.pl
Portiernia
tel.: 71 375 7958
Redaktor strony WWW
redaktor@ii.uni.wroc.pl
Projekt
MAKOS