|
Title:
|
Dominating sets in planar graphs: branch-width and exponential speed-up
|
|
Author:
|
Fomin, Fedor V.; Thilikos Touloupas, Dimitrios
|
|
Other authors:
|
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. |
|
Subject(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 |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Report |
|
Share:
|
|
