| Title | : | Conflict-Free Coloring for Interval Hypergraphs |
| Speaker | : | Dhannya S M (IITM) |
| Details | : | Mon, 25 Sep, 2017 3:30 PM @ A M Turing Hall |
| Abstract: | : | The Conflict-Free Coloring problem in hypergraphs was motivated by the problem of frequency assignment in cellular networks. It has also found applications in areas like RFID (Radio Frequency Identification) networks, robotics and computational geometry. In this problem, we are given a set system (U,F) comprising of a set of elements U and a set F of subsets of these elements. We color the elements of U such that every subset in F has at least one element that has a unique color. This problem has been studied on hypergraphs induced by geometric regions, neighborhoods in graphs, and intervals on real line etc. We studied this problem on hypergraphs induced by a subset of intervals on a real line. The status of the problem was open and the best known result was a 2-approximation algorithm. We propose an algorithm to solve this problem optimally in polynomial time. The algorithm uses dynamic programming technique and the celebrated Perfect Graph theorem. In this talk, we present the problem, its solution and few spin-off results. |
