Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
F.V. Fomin, D.M. Thilikos, in: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Fomin, Fedor V.;
Thilikos, Dimitrios M.
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 algorithms on different domination problems.
Publishing Year
Proceedings Title
Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)
LibreCat-ID
Cite this
Fomin FV, Thilikos DM. Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003). ; 2003. doi:10.1137/s0097539702419649
Fomin, F. V., & Thilikos, D. M. (2003). Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003). https://doi.org/10.1137/s0097539702419649
@inproceedings{Fomin_Thilikos_2003, title={Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up}, DOI={10.1137/s0097539702419649}, booktitle={Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)}, author={Fomin, Fedor V. and Thilikos, Dimitrios M.}, year={2003} }
Fomin, Fedor V., and Dimitrios M. Thilikos. “Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up.” In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003. https://doi.org/10.1137/s0097539702419649.
F. V. Fomin and D. M. Thilikos, “Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up,” in Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003.
Fomin, Fedor V., and Dimitrios M. Thilikos. “Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up.” Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003, doi:10.1137/s0097539702419649.
Google Scholar