Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARAMETRIC COMPLEXITY:
Reports tagged with parametric complexity:
TR18-211 | 3rd December 2018
We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>