Maximum Betweenness Centrality: Approximability and Tractable Cases

DOI10.1007/978-3-642-19094-0_4zbMath1317.68277arXiv1008.3503OpenAlexW1873406145MaRDI QIDQ3078375

Martin Fink, Joachim Spoerhase

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.3503

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Betweenness estimation in OLSR-based multi-hop networks for distributed filtering ⋮ Finding groups with maximum betweenness centrality via integer programming with random path sampling ⋮ An integer programming approach for finding the most and the least central cliques ⋮ Finding groups with maximum betweenness centrality

Cites Work

• Unnamed Item
• Unnamed Item
• Incremental deployment of network monitors based on Group Betweenness Centrality
• The hardness of approximation: Gap location
• A note on maximizing a submodular set function subject to a knapsack constraint
• The budgeted maximum coverage problem
• A faster algorithm for betweenness centrality*
• A threshold of ln n for approximating set cover
• The centrality of groups and classes