Benutzer: Gast  Login
Titel:

Embedding Graphs with Bounded Treewidth into Optimal Hypercubes

Dokumenttyp:
sfb report
Autor(en):
Volker Heun; Ernst W. Mayr
Abstract:
In this paper, we present a one-to-one embedding of a graph with bounded treewidth into its optimal hypercube. This is the first time that embeddings of graphs with a very irregular structure into hypercubes are investigated. The dilation of the presented embedding is bounded by 3*ceil(log((d+1)(t+1)))+8, where t denotes the treewidth of the graph and d denotes the maximal degree of a vertex in the graph. The given embedding is a generalization of our method to embed arbitrary binary trees into...     »
Stichworte:
parallel algorithm; simulation; network; hypercube; binary tree; treewidth; embedding
Jahr:
1995
Jahr / Monat:
1995-12-00 00:00:00
 BibTeX