返回Google圖書搜尋

Embedding Graphs with Bounded Treewidth Into Optimal Hypercubes

出版	SFB 342, 1995
URL	http://books.google.com.hk/books?id=1DiLHAAACAAJ&hl=&source=gbs_api

註釋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[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 their optimal hypercubes given in [HM93]. Moreover, if the given graph has constant treewidth or is represented by a tree-decomposition of width t, this embedding can be efficiently implemented on the optimal hypercube itself