Dominating sets in planar graphs: branch-width and exponential speed-up

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/97398

Título:	Dominating sets in planar graphs: branch-width and exponential speed-up
Autor/a:	Fomin, Fedor V.; Thilikos Touloupas, Dimitrios
Otros autores:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
Abstract:	Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known practical algorithms on different domination problems.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica -Graph minors theory -Graph algorithms -Dominating sets -Planar graphs -Branch-width -Tree-width -Dominating set -Planar graph -Fixed parameter algorithm
Derechos:
Tipo de documento:	Artículo - Versión publicada Informe
Compartir:

Fomin, Fedor V.; Thilikos Touloupas, Dimitrios

Fomin, Fedor V.; Thilikos Touloupas, Dimitrios

Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos Touloupas, Dimitrios

Thilikos Touloupas, Dimitrios; Fomin, Fedor V.

Fomin, Fedor V.; Thilikos Touloupas, Dimitrios

Coordinación

Patrocinio