Parametric Shortest Paths in Planar Graphs
| Autor: | Jaikumar Radhakrishnan, Kshitij Gajjar |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
021103 operations research Conjecture 0211 other engineering and technologies Inverse 0102 computer and information sciences 02 engineering and technology Computational Complexity (cs.CC) Binary logarithm 01 natural sciences Ackermann function Planar graph Vertex (geometry) Combinatorics symbols.namesake Computer Science - Computational Complexity 010201 computation theory & mathematics Shortest path problem symbols Parametric statistics Mathematics |
| Zdroj: | FOCS |
| DOI: | 10.48550/arxiv.1811.05115 |
| Popis: | 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$ varies in $(-\infty,+\infty)$, the piece-wise linear cost of the shortest path from $s$ to $t$ has $n^{\Omega(\log n)}$ pieces. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley \& Shah (2001) for general graphs also hold for planar graphs, thereby refuting a conjecture of Nikolova (2009). Gusfield (1980) and Dean (2009) showed that the number of pieces for every $n$-vertex graph with linear edge weights is $n^{\log n + O(1)}$. We generalize this result in two ways. (i) If the edge weights vary as a polynomial of degree at most $d$, then the number of pieces is $n^{\log n + (\alpha(n)+O(1))^d}$, where $\alpha(n)$ is the slow growing inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for $\mathbb{R}^3$, is $n^{(\log n)^2+O(\log n)}$. Comment: 39 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|