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.
| Original language | English (US) |
|---|---|
| Pages | 168-177 |
| Number of pages | 10 |
| State | Published - 2003 |
| Event | Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998 |
Other
| Other | Configuralble Computing: Technology and Applications |
|---|---|
| Country/Territory | United States |
| City | Boston, MA |
| Period | 11/2/98 → 11/3/98 |
Keywords
- Branch-width
- Dominating set
- Fixed parameter algorithm
- Planar graph
- Tree-width
ASJC Scopus subject areas
- Software
- General Mathematics