AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

Graph coloring has long been regarded as one of the most famous classic problems in computer science, with a wide range of variants, applications, and deep connections to theoretical computer science. Proper coloring of a graph is an assignment of colors to vertices, such that the endpoints of any edge in the graph are colored with different colors. One of the most important subclasses of chordal graphs is interval graphs, which are widely used in frequency allocation and resource allocation. The purpose of this research is to investigate the coloring of interval graphs. This work focuses primarily on a relaxed version of the online setting in which vertices are added one at a time along with adjacent edges, and near optimal coloring needs to be preserved after every vertex update by recoloring a limited number of already colored vertices. Although one cannot change past decisions in tight online settings, one can reduce future costs in some applications by changing past decisions. As a result, finding a trade-off between optimal coloring and the number of recolorations of previously colored vertices is interesting. Literature refers to the number of changes one needs to introduce to the maintained solution (in our case, vertex recolorings) upon an update as a recourse budget. The zero recourse budget coincides with the tight online setting where the algorithm's decisions are irrevocable.

Jennifer Gerling

+49 681 9325 1801

--email hidden

Zoom

passcode not visible

logged in users only