| Title | : | Improved Bounds and Algorithm for Online Path Coloring in Trees. |
| Speaker | : | Astha Chauhan (IITM) |
| Details | : | Tue, 14 Jun, 2016 2:00 PM @ BSB 361 |
| Abstract: | : | Graph coloring is the problem of assigning labels to the elements of a graph under some
constraints. Generally, labels given to the elements are colors. The most common variant
of graph coloring problem is the vertex coloring problem, in which we have to assign
colors to all vertices such that no two adjacent vertices get the same color. The other variants include edge coloring, face coloring and path coloring. A number of real-world problems like scheduling problems and register allocation problems in compilers can be modeled as graph coloring problems. Motivated by the problem of wavelength allocation in communication networks that make use of Wavelength Division Multiplexing (WDM), we work on the online path coloring problem in graphs. In this problem, the path coloring requests arrive in a sequence and each request has to be processed depending only on already received requests and served as soon as it arrives, with no knowledge of future requests. Given a graph G, the problem seeks to assign colors to paths of G such that all paths that share an edge of the graph get distinct colors. In our work, we consider the problem where the underlying graph G is a tree. For a given tree T, we come up with a hierarchical partitioning of its vertices with minimum number of parts, denoted by h(T), and design an O(h(T))-competitive algorithm. We then use the existing lower bound technique of Bartal and Leonardi along with a structural property of the hierarchical partition, to show a lower bound of Ω(h(T )/ log(4h(T))) on the competitive ratio of any deterministic online algorithm for this problem. |
