Raziskovalni matematični seminar - Arhiv
| 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Graph searches are important concepts of algorithmic graph theory. Besides their usage as subroutines, these algorithms have themselves become an object of study in recent years. Several researchers considered questions about the construction of search orderings with special properties. These properties include the end vertices of the search orderings as well as the spanning trees that are induced by them. In this talk, we give an overview of these questions and the known complexity results. Furthermore, we present new problems that combine the end vertices and the search trees.
Regardless of whether you have a lifelong love of mathematics or are simply curious about the subject, we invite you to join us for this engaging and thought-provoking discussion.
The seminar will also be held virtually via Zoom.
Join the Zoom Meeting HERE!
Feel free to invite any friends or colleagues who may be interested.
We look forward to (virtually) sharing the passion for math with you!
A classic result of Alekseev asserts that for connected H the Maximum Independent Set (MIS) problem in H-free graphs in NP-hard unless H is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in P_t-free graphs. The situation for forbidden subdivided claws is, however, much less understood.
During the talk we will present some recent advances in understanding the structure of graphs with no long induced claws, and their applications in designing algorithms for MIS and related problems.
Everyone is welcome and encouraged to attend.
