Simple linear time approximation algorithm for betweenness

DOI10.1016/j.orl.2012.08.008zbMath1258.90098OpenAlexW2027717506WikidataQ56486200 ScholiaQ56486200MaRDI QIDQ1939683

Yury Makarychev

Publication date: 5 March 2013

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2012.08.008

zbMATH Keywords

approximation algorithmlinear time algorithmBetweenness problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A Faster Algorithm to Update Betweenness Centrality after Node Alteration, Characterization and representation problems for intersection betweennesses, On subbetweennesses of trees: hardness, algorithms, and characterizations, Unnamed Item, Betweenness parameterized above tight lower bound, Maximizing Polynomials Subject to Assignment Constraints, A Faster Algorithm to Update Betweenness Centrality After Node Alteration

Cites Work

• Total Ordering Problem
• A Geometric Approach to Betweenness