Leírás
Variations of disjoint paths problems are of interest from both theoretical and practical perspectives. In this talk, we focus on a line of research that has developed through the interplay between theory and application. McDiarmid, Reed, Schrijver, and Shepherd studied the problem of finding the maximum number of chordless directed s–t paths in planar graphs, proposing an algorithm based on geometric and topological tools. Later, Kobayashi and Otsuki extended their approach to prove a conjecture related to reliable communication networks in the presence of disk-shaped regional failures. Interestingly, it turns out that the geometric and topological components of boths algorithms can be replaced with a purely combinatorial, abstract framework. This shift not only offers a dual perspective on the problem but also leads to a simpler, more general algorithm that encompasses all previous models.
Joint works with Vass- Barabás-Hajdú-Tapolcai and Gyimesi-Vass-Tapolcai