Anna Lindeberg: Decoding Graphs with Labeled Rooted Networks
Anna Lindeberg (Stockholm University)
Tid: On 2025-04-16 kl 10.15 - 11.15
Plats: 3418
Abstract: The starting point of this talk is an appealing class of graphs: the cographs. These graphs can be represented, or explained, by rooted trees with a 0/1-labeling which, among many other things, can guide algorithms to solve difficult problems efficiently. A reasonable and algorithmically promising generalization is to study graphs that can be explained by more intricate 0/1-labeled rooted networks. We demonstrate this idea on so-called level-1 networks. Afterwards, we proceed to outline and attack problems that arise when one tries to extend the concept to even more general networks.