Description
Az EGERVÁRY SZEMINÁRIUM következő előadója: Borsik Nóra
Cím: Vertex ordering problems in directed graphs
Az előadás ideje: 2024. október 21. hétfő 14.15, Déli tömb 3-517.
Abstract:
The talk will focus on vertex ordering problems in directed graphs
where certain constraints are imposed on the arcs that go from right
to left in the order. For instance, each vertex has lower and upper
bounds on its left out-degree (i.e., the number of arcs vu, where u is
to the left of v in the ordering). We introduce an abstract variant of
this problem, and identify a polynomial-time solvable case that has
applications in rank aggregation and scheduling. In addition to the
left out-degree bounded problem, we consider vertex ordering problems
where the left-going arcs must form a subgraph belonging to a
particular graph family, such as branchings, matchings or directed
paths. We also explore the complexity landscape of partitioning
variants of these problems, where the goal is to partition the graph
into a subgraph from a specified family and an acyclic graph.
This is a joint work with Péter Madarasi.
Minden érdeklődőt szeretettel várunk!
EGRES csoport
egres.elte.hu