Viðburðir eftir árum


ICE-TCS seminar: Bounds and Fixed Parameter Algorithms for Weighted Improper Coloring

  • 30.10.2015, 14:00 - 15:00

ICE-TCS-logo-200px

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. 



Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á ru.is eða með því að senda tölvupóst á netfangið: personuvernd@ru.is
//
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our ru.is or send an e-mail: personuvernd@ru.is