Colloquium Details
Distance Constrained Labeling on Graphs with Bounded Neighborhood Diversity
| Author: | Professor Jirka Fiala, with joint work from T. Gavenciak, D. Knop, M. Koutecky and J. Kratochvil Charles University, Prague, Czech Republic |
|---|---|
| Date: | August 13, 2015 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
We study the complexity of a group of distance-constrained graph labeling problems when parameterized by the neighborhood diversity, which is a natural graph parameter between vertex cover and clique width. Neighborhood diversity has been used to generalize and speed up FPT algorithms previously parameterized by vertex cover.
We show that the Uniform Channel Assignment problem is fixed parameter tractable when parameterized by neighborhood diversity and the largest weight. As a consequence, every L(p1,p2,...,pk)-labeling} problem is FPT when parameterized by neighborhood diversity, maximum pi and k.
Biography
Dr. Jiri (Jirka) Fiala is an associate professor in the Department of Applied Mathematics (KAM) at Charles University, Prague, Czech Republic. He is a member of the Institute of Theoretical Computer Science (ITI) and among other projects he is engaged in a research program with CIS faculty. He visited the University of Oregon in 2012/2013 as a Fulbright fellow. His research interests include graph algorithms and their complexity, restricted graph classes (bounded width, topological restrictions, geometric intersection graphs, algebraic graph theory (homomorphisms and covering projections, graph coloring and distance labeling, and Hamiltonian properties.