Vertex Coloring

Sanders/v an Stee: Approximations- und Online-Algorithmen 1 V ertex Coloring Consider a graph G = (V , E ) Edge coloring: no tw o edges that share an endpoint get the same color V erte x coloring : no tw o v ertices that are adjacent get the same color Use the minimum amount of colors This is the chromatic number Number between 1 and |V | (wh y?) Sanders/v an Stee: Approximations- und Online-Algorithmen 2 Lo wer bound It

is hard to approximate the chromatic number with approximation ratio of at most n 1 − e for e v ery fix ed e > 0 , unless NP=ZPP ZPP = Zero-error Probabilistic Polynomial time Problems for which there e xists a probabilistic T uring machine that ⁄ al w ays gi v es the correct answer , ⁄ has unbounded running time, ⁄ runs in polynomial-time on a v erage Sanders/v an Stee: Approximations- und Online-Algorithmen 3 Additi v e approximations ⁄ Instead of A ( s ) ≤ R · OPT ( s ) we require A ( s ) ≤ OPT ( s )+ c ⁄ Denote the maximum de gree of a node in G by D ( G ) ⁄ W e can al w ays color a graph with D ( G ) + 1 colors ⁄ This is sometimes required ⁄ Some graphs require f ar less colors Sanders/v an Stee: Approximations- und Online-Algorithmen 4 A graph that requires D ( G ) + 1 colors D ( G ) = 4 And no w some random te xt to k eep this slide the right side up..... Sanders/v an Stee: Approximations- und...

Website: algo2.iti.kit.edu | Filesize: -
No of Page(s): 26
Download Vertex Coloring.pdf