On the maximum betweenness improvement problem

DOI10.1016/J.ENTCS.2016.03.011MaRDI QIDQ737099zbMATH OpenOpenAlexWikidataFDO

Authors Gianlorenzo D'Angelo, Lorenzo Severini, Yllka Velaj

Publication date 5 August 2016

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

zbMATH Keywords

approximation algorithmsbetweenness centralitygraph augmentation

Mathematics Subject Classification ID

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

Recommendations

• On the maximum connectivity improvement problem
• A mixed integer linear programming formulation of the maximum betweenness problem
• An improved approximation algorithm for the maximum TSP
• Algorithms – ESA 2005
• On the fixed-parameter tractability of the maximum connectivity improvement problem
• Improved deterministic approximation algorithms for max TSP
• Improved approximation algorithms for metric MaxTSP
• An improved randomized approximation algorithm for Max TSP
• The Maximum Disjoint Routing Problem
• Better approximations for max TSP

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 5663542 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• A faster algorithm for betweenness centrality*
• A threshold of ln n for approximating set cover
• Approximating betweenness centrality in large evolving networks
• Axioms for Centrality
• Better approximation of betweenness centrality
• Emergence of Scaling in Random Networks
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Minimizing the diameter of a network using shortcut edges
• On the approximability of the link building problem
• The Effect of New Links on Google Pagerank
• The asymptotic number of labeled graphs with given degree sequences
• The design of approximation algorithms

Cited in

(7)

• Maximum betweenness centrality: approximability and tractable cases
• Hardness of bounding influence via graph modification
• Improving the betweenness centrality of a node by adding links
• Optimizing node infiltrations in complex networks by a local search based heuristic
• Generalized budgeted submodular set function maximization
• scientific article; zbMATH DE number 7204409 (Why is no real title available?)
• The parameterized complexity of centrality improvement in networks

Describes a project that uses

Uses Software

• KONECT

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q737099)