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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Fomin, Fedor V.
dc.contributor.author	Thilikos Touloupas, Dimitrios
dc.date	2002-12
dc.identifier.citation	Fomin, F., Thilikos, D. "Dominating sets in planar graphs: branch-width and exponential speed-up". 2002.
dc.identifier.uri	http://hdl.handle.net/2117/97398
dc.language.iso	eng
dc.relation	LSI-02-73-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Graph minors theory
dc.subject	Graph algorithms
dc.subject	Dominating sets
dc.subject	Planar graphs
dc.subject	Branch-width
dc.subject	Tree-width
dc.subject	Dominating set
dc.subject	Planar graph
dc.subject	Fixed parameter algorithm
dc.title	Dominating sets in planar graphs: branch-width and exponential speed-up
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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.

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