...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >On the Complexity of Optimal Hotlink Assignment
【24h】

On the Complexity of Optimal Hotlink Assignment

机译：最优热链接分配的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The concept of hotlink assignment aims at reducing the navigation effort for users of a web directory or similar structure by inserting a limited number of additional hyperlinks called hotlinks. Given an access probability distribution of the leaves of the tree representing the web site, the goal of hotlink assignment algorithms is to minimize the expected path length between the root and the leaves. We prove that this optimization problem is NP-hard, even if only one outgoing hotlink is allowed for each node. This answers a question that has been open since the first formulation of the problem in Bose et al. (Proceedings of 11th International Symposium on Algorithms and Computation (ISAAC), 2000) nine years ago. In this work we also investigate the model where hotlinks are only allowed to point at the leaves of the tree. We demonstrate that for this model optimal solutions can be computed in O(n~2) time. Our algorithm L-OPT also operates in a more general setting, where the maximum number of outgoing hotlinks is specified individually for each node. The runtime is then O(n~3). Experimental evaluation shows that L-OPT terminates within less than one second on problem instances having up to half a million nodes.
机译：热链接分配的概念旨在通过插入有限数量的称为热链接的附加超链接来减少Web目录或类似结构用户的导航工作。给定代表网站的树的叶子的访问概率分布，热链接分配算法的目标是最小化根和叶子之间的预期路径长度。我们证明，即使每个节点只允许一个传出的热链接，此优化问题也很难解决。这回答了自Bose等人首次提出该问题以来一直未解决的问题。 （九年前）（2000年第11届国际算法与计算研讨会（ISAAC）会议录）。在这项工作中，我们还研究了仅允许热链接指向树的叶子的模型。我们证明了该模型的最优解可以在O（n〜2）时间内计算出来。我们的算法L-OPT还可以在更通用的设置下运行，在该设置中，将为每个节点分别指定最大传出热链接数。那么运行时间为O（n〜3）。实验评估表明，对于多达50万个节点的问题实例，L-OPT的终止时间不到一秒钟。

著录项

  • 来源
    《Algorithmica》 |2012年第4期|p.982-1005|共24页
  • 作者

    Tobias Jacobs;

  • 作者单位

    Department of Computer Science, University of Freiburg, Georges-Kohler-Allee 79, 79110 Freiburg,Germany;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    hotlink; search tree; decision tree; graph augmentation; web graph;

    机译：热链接;搜索树;决策树;图扩充网络图;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号