On the approximability of the link building problem

DOI10.1016/j.tcs.2013.08.003zbMath1358.68225OpenAlexW1965950147MaRDI QIDQ391785

Martin Olsen, Anastasios Viglas

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.08.003

zbMATH Keywords

optimizationPageRanklink building

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Internet topics (68M11)

Related Items (4)

Improving the Betweenness Centrality of a Node by Adding Links ⋮ On the fixed-parameter tractability of the maximum connectivity improvement problem ⋮ Hardness of bounding influence via graph modification ⋮ On the maximum betweenness improvement problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing PageRank via outlinks
• Solving large FPT problems on coarse-grained parallel machines
• A Constant-Factor Approximation Algorithm for the Link Building Problem
• Maximizing PageRank with New Backlinks
• An analysis of approximations for maximizing submodular set functions—I
• Deeper Inside PageRank
• Ergodic Control and Polyhedral Approaches to PageRank Optimization
• The Effect of New Links on Google Pagerank

This page was built for publication: On the approximability of the link building problem