Advice Complexity of the Online Coloring Problem

Autor:	Andreas Sprock, Walter Unger, Sebastian Seibert
Jazyk:	angličtina
Rok vydání:	2013
Předmět:	FARBENPROBLEME (GRAPHENTHEORIE) COMPLEXITY CLASSES (THEORETICAL COMPUTER SCIENCE) Combinatorics Greedy coloring Indifference graph ALGORITHMIC COMPLEXITY (MATHEMATICS) Data processing computer science Pathwidth Computer Science::Discrete Mathematics Chordal graph FOS: Mathematics Graph coloring KOMPLEXITÄTSKLASSEN (THEORETISCHE INFORMATIK) ddc:510 Computer Science::Data Structures and Algorithms ComputingMilieux_MISCELLANEOUS ComputingMethodologies_COMPUTERGRAPHICS Mathematics Discrete mathematics Mathematics::Combinatorics Interval graph Complete coloring Maximal independent set ddc:004 ALGORITHMISCHE KOMPLEXITÄT (MATHEMATIK) COLOURING OF GRAPHS (GRAPH THEORY) MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj:	Proceedings of the 8th International Conference on Algorithms and Complexity Lecture Notes in Computer Science ISBN: 9783642382321 CIAC
DOI:	10.3929/ethz-a-010889887
Popis:	We study online algorithms with advice for the problem of coloring graphs which come as input vertex by vertex. We consider the class of all 3-colorable graphs and its sub-classes of chordal and maximal outerplanar graphs, respectively.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6739558b40c132c1da9d8ccc58459f72 Zobrazit plný text záznamu