A note on domino treewidth
| Autor: | Hans L. Bodlaender |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1999 |
| Předmět: | |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol 3, Iss 4 (1999) |
| Druh dokumentu: | article |
| ISSN: | 1462-7264 1365-8050 71745289 |
| Popis: | In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c k,d. This note gives a new simple proof of this fact, with a better bound for c k,d, namely (9k+7)d(d+1) -1. It is also shown that a lower bound of Ω(kd) holds: there are graphs with domino treewidth at least 1/12 × kd-1, treewidth at most k, and maximum degree at most d, for many values k and d. The domino treewidth of a tree is at most its maximum degree. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|