Dokt-seminar-l May 2019

dokt-seminar-l@kam.mff.cuni.cz

1 participants
4 discussions

no seminar tomorrow & send me your handouts
by Robert Samal 22 May '19

22 May '19

Hi all, there is no seminar tomorrow. Please, use part of the time thus spared to send me a handout from your talk, I want to update the seminar's webpage. Thanks, R -- Robert Šámal IÚUK MFF UK -- CSI of Charles University

1 0

doct. seminar May 16
by Robert Samal 15 May '19

15 May '19

Hi all, this week we will have seminar given by a vising grad student from Slovenia. The seminar is in the usual time slot. I'm writing this a bit earlier in case you may want to discuss something (I believe she only stays this week). Title: On the End-Vertex Problem of Graph Searches Speaker: Nevena Pivač (University of Primorska) End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. In the lecture we will present a selection of known and new results related to end vertices of various graph searches. The problem of deciding whether a given vertex of a graph is an end vertex of a particular search was first introduced by Corneil, Köohler, and Lanlignel in 2010. There they showed that this problem is in fact NP-complete for LBFS on weakly chordal graphs. A similar result for BFS was obtained by Charbit, Habib and Mamcarz in 2014. Regarding new results, we prove that the end-vertex problem is NP-complete for MNS on weakly chordal graphs and for MCS on general graphs. Moreover, building on previous results, we show that this problem is linear-time solvable for various searches on split and unit interval graphs. Joint work with Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Robert Scheffler, Martin Strehler. Preprint available at https://arxiv.org/abs/1810.12253. -- Robert Šámal IÚUK MFF UK -- CSI of Charles University

1 1

doct. seminar Thu May 9
by Robert Samal 08 May '19

08 May '19

Hi all, tomorrow we will have opportunity to hear Jakub Pekárek speaking about graph limits and their applications to interval graph: Huda Chuangpishit, Mahya Ghandehari, Matthew Hurshman, Jeannette Janssen, Nauzer Kalyaniwalla: Linear embeddings of graphs and graph limits See you tomorrow! R -- Robert Šámal IÚUK MFF UK -- CSI of Charles University

1 0

no doct.seminar today!
by Robert Samal 02 May '19

02 May '19

Hi all, just a reminder -- there is no seminar today. We are looking forward to a talk by Jakub Pekárek next week -- on the topic of graph limits. Best wishes, R -- Robert Šámal IÚUK MFF UK -- CSI of Charles University

1 0

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

Dokt-seminar-l May 2019