Title:
|
Dominating sets and local treewidth
|
Author:
|
Thilikos Touloupas, Dimitrios; Fomin, Fedor V.
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
It is known that the treewidth of a planar graph with a
dominating set of size d is O(sqrt{d}) and this fact is used as the
basis for several fixed parameter algorithms on planar graphs.
An interesting question motivating our study is if similar bounds can be
obtained for larger minor closed graph families. We say that a graph
family F has the {domination-treewidth property} if there is
some function f(d) such that every graph G in F with dominating set of
size at most d has treewidth at most f(d). We show that a minor-closed
graph family F has the domination-treewidth property if and only if F
has bounded local treewidth. This result has important algorithmic
consequences. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Planar graphs -Dominating sets -Local treewidth |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|