Linear-time graph distance and diameter approximation

DOI10.1111/ITOR.12236MaRDI QIDQ2827756zbMATH OpenOpenAlexFDO

Authors R. C. S. Machado, Celina M. H. de Figueiredo

Publication date 21 October 2016

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/itor.12236

zbMATH Keywords

breadth first searchdistance in graphsgraph diameterlinear-time algorithm

Mathematics Subject Classification ID

Distance in graphs (05C12) Programming involving graphs or networks (90C35)

Recommendations

• Diameter determination on restricted graph families
• scientific article; zbMATH DE number 1262798
• Fast approximation algorithms for the diameter and radius of sparse graphs
• On the power of BFS to determine a graph's diameter
• Better approximation algorithms for the graph diameter

Cites work

• On the power of BFS to determine a graph's diameter

Cited in

(12)

• A linear-space algorithm for distance preserving graph embedding
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• Simple linear time approximation algorithm for betweenness
• scientific article; zbMATH DE number 2086230 (Why is no real title available?)
• On the power of BFS to determine a graph's diameter
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Fast and Simple Approximation of the Diameter and Radius of a Graph
• A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
• Approximate Distance Queries in Disk Graphs
• Efficient Point-to-Point Resistance Distance Queries in Large Graphs
• The diameter of AT‐free graphs
• Path eccentricity of k-AT-free graphs and application on graphs with the consecutive ones property

This page was built for publication: Linear-time graph distance and diameter approximation

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