Simple linear time approximation algorithm for betweenness

DOI10.1016/J.ORL.2012.08.008MaRDI QIDQ1939683zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithmBetweenness problemlinear time algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1875419
• Linear-time graph distance and diameter approximation
• A Practical Shortest Path Algorithm with Linear Expected Time
• A linear time algorithm for determining almost bipartite graphs
• Approximating the Metric TSP in Linear Time
• Approximating the metric TSP in linear time
• STACS 2004
• Simpler computation of single-source shortest paths in linear average time
• scientific article; zbMATH DE number 7759280
• Linear time algorithm for computing a small biclique in graphs without long induced paths

Cites work

• A Geometric Approach to Betweenness
• Total Ordering Problem

Cited in

(12)

• A linear-time algorithm for finding an ambitus
• Betweenness parameterized above tight lower bound
• On subbetweennesses of trees: hardness, algorithms, and characterizations
• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Maximizing Polynomials Subject to Assignment Constraints
• Approximation schemes for the betweenness problem in tournaments and related ranking problems
• A Geometric Approach to Betweenness
• scientific article; zbMATH DE number 1875419 (Why is no real title available?)
• A faster algorithm to update betweenness centrality after node alteration
• scientific article; zbMATH DE number 7758347 (Why is no real title available?)
• A geometric approach to betweenness
• Characterization and representation problems for intersection betweennesses

This page was built for publication: Simple linear time approximation algorithm for betweenness

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