Anna Lindeberg: Decoding Graphs with Labeled Rooted Networks

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.