Dominating sets in planar graphs: Branch-width and exponential speed-up

Fedor V. Fomin, Dimitrios M. Thilikos

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
Number of pages10
StatePublished - 2003
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998


OtherConfiguralble Computing: Technology and Applications
Country/TerritoryUnited States
CityBoston, MA


  • Branch-width
  • Dominating set
  • Fixed parameter algorithm
  • Planar graph
  • Tree-width

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Dominating sets in planar graphs: Branch-width and exponential speed-up'. Together they form a unique fingerprint.

Cite this