Noticias en español
Abstract:
In the precedence-constrained perfect matching problem, one needs to incrementally build a matching, whereby the order in which edges join the matching is subject to precedence constraints. Given a graph G = (V, E), a precedence constraint is a pair (X, e) with e being an edge and X a set of vertices, meaning that e may only be added to the matching after covering at least one vertex in X. In this talk, I will introduce C-canonical precedence constraints, where an edge may join a matching if both end-vertices have (shortest path) distance at most C to the current matching. I will talk about the complexity of the problem for different values of C and for different graph classes and present some open questions.
Date: Aug 21, 2024 at 15:00:00 h
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Corinna Mathwieser
Affiliation: RWTH Aachen University, Germany
Coordinator: José Verschae
Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.
Speaker: Corinna Mathwieser
Affiliation: RWTH Aachen University, Germany
Coordinator: José Verschae
Abstract:
PDF
