Mahajan, Meena ; Nimbhorkar, Prajakta ; Tawari, Anuj (2019) Shortest path length with bounded-alternation $$(\min ,+)$$ ( min , + ) formulas International Journal of Advances in Engineering Sciences and Applied Mathematics, 11 (1). pp. 68-74. ISSN 0975-0770
Full text not available from this repository.
Official URL: http://doi.org/10.1007/s12572-018-0229-6
Related URL: http://dx.doi.org/10.1007/s12572-018-0229-6
Abstract
We study bounded-depth (min,+) formulas computing the shortest path polynomial. For depth 2d with d≥2, we obtain lower bounds parameterized by certain fan-in restrictions on + gates except those at the bottom level. For depth 4, in two regimes of the parameter, the bounds are tight.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer Nature Switzerland AG. |
| Keywords: | Formulas; Circuits; Lower bounds; Tropical semiring; Shortest path |
| ID Code: | 128036 |
| Deposited On: | 14 Oct 2022 11:26 |
| Last Modified: | 14 Oct 2022 11:26 |
Repository Staff Only: item control page
