Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1393010,
author = {Cagirici, Onur and Hliněný, Petr and Roy, Bodhayan},
address = {Dagstuhl},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21},
edition = {LIPIcs 93},
keywords = {polygon visibility graph; graph coloring; NP-completeness},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl},
isbn = {978-3-95977-055-2},
pages = {"21:1"-"21:14"},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
title = {On Colourability of Polygon Visibility Graphs},
year = {2018}
}
TY - JOUR
ID - 1393010
AU - Cagirici, Onur - Hliněný, Petr - Roy, Bodhayan
PY - 2018
TI - On Colourability of Polygon Visibility Graphs
PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY - Dagstuhl
SN - 9783959770552
KW - polygon visibility graph
KW - graph coloring
KW - NP-completeness
N2 - We study the problem of colouring the visibility graphs of polygons. In particular, we provide a polynomial algorithm for 4-colouring of the polygon visibility graphs, and prove that the 6-colourability question is already NP-complete for them.
ER -
CAGIRICI, Onur, Petr HLINĚNÝ a Bodhayan ROY. On Colourability of Polygon Visibility Graphs. Online. In \textit{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}. LIPIcs 93. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018, s.~''21:1''-''21:14'', 14 s. ISBN~978-3-95977-055-2. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.21.
|
