×

Graph coloring problems. (English) Zbl 1214.05037

Paschos, Vangelis Th., Combinatorial optimization. Volume 2: Paradigms of combinatorial optimization. Problems and new approaches. London: ISTE; Hoboken, NJ: John Wiley & Sons (ISBN 978-1-84821-148-3/hbk; 978-1-84821-146-9/set). 265-310 (2010).
Summary: We present the basic concepts of colorings as well as a series of variations and generalizations prompted by various scheduling problems including drawing up school timetables. A few recent exact algorithms and some heuristics will be presented. In particular we will give an outline of methods based on the tabu search for finding approximate solutions for large problems. Lastly, we mention application of colorings to various problems, including computer file transfers and production systems. This text is an extended version of [D. de Werra and D. Kobler, RAIRO, Oper. Res. 37, No. 1, 29–66 (2003; Zbl 1062.90026)].
For the entire collection see [Zbl 1196.90012].

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1062.90026
PDFBibTeX XMLCite