ICE-TCS seminar: Bounds and Fixed Parameter Algorithms for Weighted Improper Coloring
Friday, 30 October 2015: Tomas Ken Magnusson (Reykjavik University) will deliver an ICE-TCS seminar. The talk, which is entitled Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring, will be held at 2pm in room M1.02 at Reykjavik University.
Abstract: In this talk, I will discuss the weighted improper coloring problem, a generalization of defective coloring. I will present some hardness results, amongst which that weighted improper coloring is not fixed-parameter tractable
when parameterized by pathwidth. I will generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally I give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and
maximum degree and when parameterized by treewidth and precision of edge weights. This yields a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.
The talk is based on joint work with Bjarki Agust Gudmundsson and Bjorn Orri Saemundsson that was presented at ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science, Firenze, Italy.
