Predavatelj: Robert SCHEFFLER
Doktorski študent na Katedri za diskretno matematiko in temelje računalništva na Brandenburški tehniški univerzi v Cottbusu v Nemčiji.

Naslov: The Distance Orientation Problem

Povzetek:
We study the Distance Orientation Problem (DOP) which is motivated by an applications in the field of computer vision. Given a weighted graph, the question is whether there is a function that assigns heights to the vertices, such that the absolute difference between the heights of adjacent vertices is equal to the weight of the edge between these vertices. This problem can also be formulated as the task of finding a special orientation of the graph. We will present some complexity results for the DOP on planar graphs. Furthermore, we will see that outerplanar embeddings have a special property in respect to this problem, which characterizes them.

--------------------------------------------------------------

Predavatelj: Jesse BEISEGEL
Doktorski študent na Brandenburški tehniški univerzi v Cottbusu v Nemčiji

Naslov: Characterising AT-Free Graphs with BFS

Povzetek:
An asteroidal triple free graph is a graph such that for every independent triple of vertices no path between any two avoids the third. In a recent result, these graphs were characterised through a linear vertex ordering called an AT-free order. Here, we use techniques from abstract convex geometry to improve on this result by giving a vertex order characterisation with stronger structural properties and thus resolve an open question Corneil and Stacho. These orderings are generated by a modification of BFS which runs in polynomial time. Furthermore, we give a linear time algorithm which employs multiple applications of (L)BFS to compute AT-free orders in claw-free AT-free graphs and a generalisation of these.

--------------------------------------------------------------

Seminarja bosta predstavjena v angleškem jeziku.

Vabljeni!