Tato práce je pokračováním ročníkového projektu. Úkolem je nastudovat a implementovat First Fit algoritmus a upravený algoritmus pro bipartitní grafy. Student by měl popsat vlasnosti obou algoritmů na třídě bip. grafů a softwareovým experimentem porovnat jejich výsledky.
Seznam odborné literatury
Borodin, El-Yaniv: Online Computation and Competitive Analysis (1998)
Fiat, Woeginger: Online Algorithms (1998, LNCS 1442)
odborné články z časopisů a internetu
Předběžná náplň práce
Instancí problému on-line barvení grafu je graf a pořadí jeho vrcholů, algoritmus potom barví popořadě vrcholy a jako informaci zná graf indukovaný předchozími vrcholy. Přirozeným algoritmem je First Fit, který obarví vrchol první přípustnou barvou. Tento algoritmus má ale slabiny, poměr mezi nalezeným a optimálním řešením může být až n/4, kde n je počet vrcholů grafu, a to i pro grafy bipartitní. Pro ty je ale znám algoritmus s logaritmickým aproximačním faktorem.
Předběžná náplň práce v anglickém jazyce
Instance of the on-line graph coloring problem is a graph together with a permutation of its vertices (viewed as a linear ordering of the vertex set). The goal is to color the graph with vertices taken in the given order using the information of the subgraph induced by previous vertices. The most natural algoritm is the First Fit algorithm using in each step the first possible color. Unfortunately the ratio betweem optimum and obtained number of colors can be n/4, even for bipartite graphs. On the other hand, there is an algorithm with logaritmic aproximation factor for this class of graphs.
- zadáno a potvrzeno stud. odd.