BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UNIFR/WEBMASTER//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTSTART;VALUE=DATE:20181204T171500
DTEND;VALUE=DATE:20181204T171500
UID:5787@agenda.unifr.ch
DESCRIPTION:A typical graph modification problem aims to modify a graph G, via a small number of operations from a specified set S, into some other graph H that has a certain desired property, which usually describes a certain graph class G to which H must belong. In this way a variety of classical graph-theoretic problems is captured. For instance, if only k vertex deletions are allowed and H must be an independent set or a clique, we obtain the Independent Set or Clique problem, respectively.\nNow, instead of fixing a particular graph class G, we fix a certain graph parameter  π. That is, given a graph G, a set S of one or more graph operations and an integer k, we ask whether G can be transformed into a graph G' by using at most k operations from S, such that π(G') ≤ π(G)-d for some threshold d ≥ 0.  Such problems are called blocker problems, as the set of vertices or edges involved can be seen as ``blocking''  some desirable graph property (such as being colorable with only a few colors). Identifying the part of the graph responsible for a significant decrease of the parameter under consideration gives crucial information on the graph.\nBlocker problems have been given much attention over the last few years. In this talk, I will give an overview of recent results on this topic.
SUMMARY:Prof. Bernard Ries (Uni Fribourg): On some graph modification problems
CATEGORIES:Colloque / Congrès / Forum
LOCATION:PER 08\, Phys 2.52\, Chemin du Musée 3\, 1700 Fribourg
URL;VALUE=URI:https://agenda.unifr.ch/e/fr/5787
END:VEVENT
END:VCALENDAR