Thumbnail
Access Restriction
Subscribed

Author Jacobs, Tobias
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Search tree ♦ Approximation ♦ Hotlink
Abstract The concept of hotlink assignment aims at enhancing the structure of Web sites such that the user's expected navigation effort is minimized. We concentrate on sites that are representable by trees and assume that each leaf carries a weight representing its popularity. The problem of optimally adding at most one additional outgoing edge (“hotlink”) to each inner node has been widely studied. A considerable number of approximation algorithms have been proposed and worst-case bounds for the quality of the computed solutions have been given. However, only little is known about the practical behavior of most of these algorithms. This article contributes to closing this gap by evaluating all recently proposed strategies experimentally. Our experiments are based on trees extracted from real Web sites, as well as on synthetic instances. The latter are generated by a new method that simulates the growth of a Web site over time. Finally, we present a new heuristic that is easy to implement and exhibits excellent behavior in practice.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-03-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 15
Page Count 18
Starting Page 1.1
Ending Page 1.18


Open content in new tab

   Open content in new tab
Source: ACM Digital Library