Diameter 2 vs 3

Given a graph G=(V,E)G = (V, E), distinguish between diameter 2 and diameter 3. In other words, approximate diameter within a factor of 4/3−ϵ4/3-\epsilon.

Parameters

  • nn: number of nodes
  • mm: number of edges

Related Problems

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table