Graph Searching, Elimination Trees, and a Generalization of Bandwidth |
| |
Authors: | Fedor V Fomin Pinar Heggernes Jan Arne Telle |
| |
Affiliation: | (1) Department of Informatics, University of Bergen, N-5020 Bergen, Norway |
| |
Abstract: | The bandwidth minimization problem has a long history and a number of practical applications.
In this paper we introduce a natural extension of bandwidth to partially ordered layouts.
We consider this extension from three main viewpoints: graph searching,
tree decompositions, and elimination orderings.
The three graph parameters pathwidth, profile, and bandwidth related to linear layouts
can be defined by variants of graph searching using a standard fugitive.
Switching to an inert fugitive, the two former parameters are extended to
treewidth and fill-in, and our first viewpoint considers the
analogous tree-like extension that arises from the bandwidth variant.
Bandwidth also has a definition in terms of ordered path decompositions,
and our second viewpoint extends this in a natural way to ordered
tree decompositions.
In showing that both extensions are equivalent we employ the third viewpoint of
elimination trees, as used in the field of sparse matrix computations.
We call the resulting parameter the treespan of a graph and
prove some of its combinatorial and algorithmic properties. |
| |
Keywords: | Bandwidth Graph searching Elimination tree Tree decomposition Chordal graph |
本文献已被 SpringerLink 等数据库收录! |
|