View source for Constant sensitivity (4/3)-approximate incremental diameter

{{DISPLAYTITLE: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 == 

<pre>n: number of nodes
m: number of edges</pre>

== Table of Algorithms == 

Currently no algorithms in our database for the given problem.

== Reductions FROM Problem == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Problem !! Implication !! Year !! Citation !! Reduction

|-

| [[CNF-SAT]] ||  style="text-align:left;" | assume: SETH<br/>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 || [[Reduction from CNF-SAT to constant sensitivity (4/3)-approximate incremental diameter|link]]
|-
|}