constant sensitivity (4/3)-approximate incremental diameter (Graph Metrics)

Description

Approximate the diameter of a graph decrementally within a factor of 4/3, with a constant sensitivity of $K(\epsilon, t)$, i.e. when a $K(\epsilon, t)$ edges are removed.

Related Problems

Generalizations: Decremental Diameter

Related: Median, Radius, Diameter, Diameter 2 vs 3, Diameter 3 vs 7, Approximate Diameter, 1-sensitive (4/3)-approximate decremental diameter, 1-sensitive decremental diameter, 1-sensitive (4/3)-approximate decremental eccentricity

Parameters

$n$: number of nodes

$m$: number of edges

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
CNF-SAT	assume: SETH then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$	2017	https://arxiv.org/pdf/1703.01638.pdf	link