| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331938 | Information Processing Letters | 2005 | 4 Pages |
Abstract
Recently Fomin, Heggernes and Telle [Algorithmica 41 (2004) 73] introduced the notion of the treespan of a graph as a natural extension of the well-known bandwidth. They motivate this new concept from different viewpoints involving graph searching, tree decompositions and elimination orderings. In the present paper we prove several lower bounds on the treespan.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dieter Rautenbach,