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.
|