On the maximum betweenness improvement problem

DOI10.1016/j.entcs.2016.03.011zbMath1344.68174OpenAlexW2338639814WikidataQ113317693 ScholiaQ113317693MaRDI QIDQ737099

Gianlorenzo D'Angelo, Yllka Velaj, Lorenzo Severini

Publication date: 5 August 2016

Full work available at URL: https://doi.org/10.1016/j.entcs.2016.03.011

zbMATH Keywords

approximation algorithmsgraph augmentationbetweenness centrality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

Improving the Betweenness Centrality of a Node by Adding Links ⋮ Hardness of bounding influence via graph modification ⋮ Optimizing node infiltrations in complex networks by a local search based heuristic ⋮ Unnamed Item ⋮ Generalized budgeted submodular set function maximization

Uses Software

• KONECT

Cites Work

• On the approximability of the link building problem
• The asymptotic number of labeled graphs with given degree sequences
• A faster algorithm for betweenness centrality*
• The Design of Approximation Algorithms
• Emergence of Scaling in Random Networks
• A threshold of ln n for approximating set cover
• Minimizing the Diameter of a Network Using Shortcut Edges
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• A critical point for random graphs with a given degree sequence
• Axioms for Centrality
• Approximating Betweenness Centrality in Large Evolving Networks
• Better Approximation of Betweenness Centrality
• The Effect of New Links on Google Pagerank
• Unnamed Item
• Unnamed Item

This page was built for publication: On the maximum betweenness improvement problem