Strategies for Hotlink Assignments
Strategies for Hotlink Assignments
复制标题
盗链分配策略
DOI：
10.1007/3-540-40996-3_3
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
L. Gąsieniec
中科院分区：
文献类型：
--
作者：
P. Bose;E. Kranakis;D. Krizanc;Miguel Vargas Martin;J. Czyzowicz;A. Pelc;L. Gąsieniec
考虑DAG(有向无环图)G=(V，E)，其表示通过链接E连接的网页的集合V。所有网页都可以从指定的源页到达，由G的源节点S表示。每个网页携带表示其被访问频率的权重。通过添加热链接，每个页面最多一个，我们感兴趣的是最大限度地减少从源页面访问一组选定网页所需的预期步骤数。对于任意的DAG，我们证明了该问题是NP完全的。
我们还给出了分配热链接的算法，以及从位于完全二叉树根部的源页面S到达树叶的预期步数的上下界。根据概率分布(任意的、均匀的、zipf)，期望步数最多为cċn，其中c是小于1的常数。对于几何分布，我们说明如何获得恒定的平均步数。
Consider a DAG (directed acyclic graph) G = (V, E) representing a collection V of web pages connected via links E. All web pages can be reached from a designated source page, represented by a source node s of G. Each web page carries a weight representative of the frequency with which it is visited. By adding hotlinks, at most one per page, we are interested in minimizing the expected number of steps needed to visit a selected set of web pages from the source page. For arbitrary DAGs we show that the problem is NP-complete.
We also give algorithms for assigning hotlinks, as well as upper and lower bounds on the expected number of steps to reach the leaves from the source page s located at the root of a complete binary tree. Depending on the probability distribution (arbitrary, uniform, Zipf) the expected number of steps is at most c ċ n, where c is a constant less than 1. For the geometric distribution we show how to obtain a constant average number of steps.