Answers are grounded in this paper and cite their sources.
We construct a family of planar graphs {G n } n≥4 , where G_n has n vertices including a source vertex s, a sink vertex t, and edge weights that change linearly with a parameter λ such that, as λ varies in (-∞,+∞), the piece-wise linear cost of the shortest path from s to t has n Ω(logn) pieces. This shows that lower bounds obtained by Carstensen (1983) and Mulmuley & Shah (2001) for general graphs also hold for planar graphs, 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 logn+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(logn+(α(n)+O(1)) d ) , where α(n) is the inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for R 3 , is n((logn) 2 +O(logn)).
No takes yet. Share an insight, caveat, or question.
Gajjar et al. (2019) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: