Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
The work
| Authors | Fedor V. Fomin; Dimitrios M. Thilikos |
|---|---|
| Editors | |
| Type | article |
| Year | 2006 |
| Citekey | fomin2006dominating |
Where it appeared
| Published in | SIAM Journal on Computing |
|---|---|
| Publisher | Society for Industrial & Applied Mathematics (SIAM) |
| Volume | 36 |
| Issue | 2 |
| Pages | 281--309 |
Identifiers
| DOI | 10.1137/s0097539702419649 |
|---|---|
| ISSN | 0097-5397 |
Access
| Landing page | https://doi.org/10.1137/s0097539702419649 |
|---|
From crossref.
Abstract
We introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of Robertson and Seymour on graph minors. Graph minors provide a list of powerful theoretical results and tools. However, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. In this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. Our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. By using this approach, we show that the k-dominating set problem on planar graphs can be solved in time O(2 15.13 \sqrt k + n 3 ).
How it got here
| How it got here | agent via crossref |
|---|---|
| Added | 2026-10-23 15:55 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@article{fomin2006dominating,
title = {Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up},
author = {Fedor V. Fomin and Dimitrios M. Thilikos},
year = {2006},
journal = {SIAM Journal on Computing},
publisher = {Society for Industrial \& Applied Mathematics (SIAM)},
volume = {36},
number = {2},
pages = {281--309},
issn = {0097-5397},
doi = {10.1137/s0097539702419649},
}
This record lives at https://refs.drheap.org/fomin2006dominating/ and will keep doing so.