Carregant...
Carregant...

Vés al contingut (premeu Retorn)

3-colorability of pseudo-triangulations

Autor
Aichholzer, O.; Aurenhammer, F.; Hackl, T.; Huemer, C.; Pilz, A.; Vogtenhuber, B.
Tipus d'activitat
Article en revista
Revista
International journal of computational geometry and applications
Data de publicació
2015
Volum
25
Número
4
Pàgina inicial
283
Pàgina final
298
DOI
https://doi.org/10.1142/S0218195915500168 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/85279 Obrir en finestra nova
URL
http://www.worldscientific.com/worldscinet/ijcga Obrir en finestra nova
Resum
Deciding 3-colorability for general plane graphs is known to be an NP-complete problem. However, for certain families of graphs, like triangulations, polynomial time algorithms exist. We consider the family of pseudo-triangulations, which are a generalization of triangulations, and prove NP-completeness for this class. This result also holds if we bound their face degree to four, or exclusively consider pointed pseudo-triangulations with maximum face degree five. In contrast to these completenes...
Citació
Aichholzer, O., Aurenhammer, F., Hackl, T., Huemer, C., Pilz, A., Vogtenhuber, B. 3-colorability of pseudo-triangulations. "International journal of computational geometry and applications", 2015, vol. 25, núm. 4, p. 283-298.
Paraules clau
Pseudo-triangulation, 3-colorability, Face Degree
Grup de recerca
DCCG - Grup de recerca en geometria computacional, combinatoria i discreta

Participants

  • Aichholzer, Oswin  (autor)
  • Aurenhammer, Franz  (autor)
  • Hackl, Thomas  (autor)
  • Huemer, Clemens  (autor)
  • Pilz, Alexander  (autor)
  • Vogtenhuber, Birgit  (autor)

Arxius