登入選單

返回Google圖書搜尋

Salvage-embeddings of Complete Trees

University of Massachusetts at Amherst. Department of Computer and Information Science

出版	University of Massachusetts at Amherst, Department of Computer and Information Science, 1992
URL	http://books.google.com.hk/books?id=mQKKHAAACAAJ&hl=&source=gbs_api

註釋

Abstract: "A salvage-embedding (S-embedding) maps an M-leaf complete binary tree G into an (N> M)-leaf complete binary tree H, the fraction G of whose leaves have been labeled Good. The S-embedding maps leaves of G one-to-one to Good leaves of H; it may be many-to-one on internal nodes. The quality of an S-embedding depends on its harvest, the ratio H = [subscript def] M/GN, and its congestion, the largest number of edges of G that get 'routed' across the same edge of H. We study three scenarios. In the worst-case scenario: given any target harvest H [