✦ LIBER ✦

On the advice complexity of the online L(2,1)-coloring problem on paths and cycles

✍ Scribed by Bianchi, Maria Paola; Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Krug, Sacha; Steffen, Björn

Book ID: 126902028
Publisher: Elsevier Science
Year: 2014
Tongue: English
Weight: 574 KB
Volume: 554
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2014.06.027

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Effect of Number of Hamiltonian Path

The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem

✍ Manber, Udi; Tompa, Martin 📂 Article 📅 1984 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 900 KB

On the advice complexity of online bipar

On the advice complexity of online bipartite matching and online stable marriage

✍ Miyazaki, Shuichi 📂 Article 📅 2014 🏛 Elsevier Science 🌐 English ⚖ 233 KB

On the circular-L(2, 1)-labelling for st

On the circular-L(2, 1)-labelling for strong products of paths and cycles

✍ Tang, Yuan Yan; Xu, Xiaodong; Lang, Fangnian; Yeh, Roger K.; Shao, Zehui 📂 Article 📅 2014 🏛 The Institution of Engineering and Technology 🌐 English ⚖ 404 KB

On the complexity of path problems in pr

On the complexity of path problems in properly colored directed graphs

✍ Donatella Granata, Behnam Behdani, Panos M. Pardalos 📂 Article 📅 2011 🏛 Springer US 🌐 English ⚖ 445 KB

On the complexity of the black-and-white

On the complexity of the black-and-white coloring problem on some classes of perfect graphs

✍ Kloks, Ton; Poon, Sheung-Hung; Tsai, Feng-Ren; Wang, Yue-Li 📂 Article 📅 2014 🏛 Elsevier Science 🌐 English ⚖ 395 KB

A note on the complexity of longest path

A note on the complexity of longest path problems related to graph coloring

✍ P.M. Pardalos; A. Migdalas 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 194 KB

In this note, we show that some problems related to the length of the longest simple path from a given vertex in a graph are NP-complete. We also discuss an extension to the graph coloring problem.