Nagy-György Judit: On the advice complexity of coloring bipartite graphs and two-colorable hypergraphs. In: Acta cybernetica, (23) 3. pp. 929-938. (2018)
Előnézet |
Cikk, tanulmány, mű
actacyb_23_3_2018_13.pdf Letöltés (344kB) | Előnézet |
Absztrakt (kivonat)
In the online coloring problem the vertices are revealed one by one to an online algorithm, which has to color them immediately as they appear. The advice complexity attempts to measure how much knowledge of the future is neccessary to achieve a given competitive ratio. Here, we examine coloring of bipartite graphs, proper and the conflict-free coloring of k-uniform hypergraphs and we provide lower and upper bounds for the number of bits of advice to achieve the optimal cost. For bipartite graphs the upper bound n − 2 is tight. For the proper coloring, n − 2k bits are necessary and n − 2 bits are sufficient, while for the conflict-free coloring case n − 2 bits of advice are neccessary and sufficient to color optimally if k > 3.
| Mű típusa: | Cikk, tanulmány, mű |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Acta cybernetica |
| Dátum: | 2018 |
| Kötet: | 23 |
| Szám: | 3 |
| ISSN: | 0324-721X |
| Oldalak: | pp. 929-938 |
| Nyelv: | angol |
| Kiadás helye: | Szeged |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/55467/ |
| Kulcsszavak: | Hipergráf, Gráf |
| Megjegyzések: | Bibliogr.: p. 937-938. ; összefoglalás angol nyelven |
| Szakterület: | 01. Természettudományok 01. Természettudományok > 01.01. Matematika 01. Természettudományok > 01.02. Számítás- és információtudomány |
| Feltöltés dátuma: | 2018. nov. 08. 09:04 |
| Utolsó módosítás: | 2022. jún. 21. 08:31 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/55686 |
 |
Tétel nézet |
