Colloquium Details
Rising from stars and lines: About Two graph reconstruction problems
| Author: | Jan Kratochvil Charles University, Prague, Czech Republic |
|---|---|
| Date: | April 14, 2011 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | Andrzej Proskurowski |
Abstract
The famous Ulam's conjecture claims that any graph on at least 3 vertices is uniquely determined (up to isomorphism) from the deck of its single-vertex deleted subgraphs. The talk is about two related concepts - reconstructing graphs from the closed neighborhoods (sometimes referred to as the stars) of its vertices, and reconstructing graphs from their line structures. Both cases are treated from the complexity point of view, i.e., we study the question "Given a set system, does there exist a graph whose star system (line system) is the given one?" In both cases unique reconstruction does not hold for general graphs, but it does for some special graph classes. And polynomial time algorithms are designed based on the uniqueness. Several open problems will be mentioned.
The first part of the talk is based on a joint work with Fedor V. Fomin, Daniel Lokshtanov, Federico Mancini, and Jan Arne Telle from Bergen, the second part on a work of Jozef Jirasek and Pavel Klavik from Prague.
Biography
Jan Kratochvil is a full professor and head of the Department of Applied Mathematics at Charles University in Prague, Czech Republic. His major area of work is theoretical computer science, in particular algorithms and complexity in graph theory. He received his Ph.D. at Charles University in 1987 for a thesis about domination and codes in graphs.