4 papers
A Reflection Calculus for Bar Induction and the Linearity of Consistency Strength Ordering
Fedor Pakhomov, Vlad Lazar
We introduce a novel extension of reflection calculus, , to analyze a family of extensions of generated by uniform -model and syntactic reflec…
On Computing Top- Simple Shortest Paths from a Single Source
Mattia D'Emidio, Gabriele Di Stefano
We investigate the problem of computing the top- simple shortest paths in weighted digraphs. While the single-pair variant -- finding the top- simple shortest paths between t…
Hardness, Approximability, and Fixed-Parameter Tractability of the Clustered Shortest-Path Tree Problem
Mattia D'Emidio, Luca Forlizzi, Daniele Frigioni +2
Given an -vertex non-negatively real-weighted graph , whose vertices are partitioned into a set of clusters, a \emph{clustered network design problem} on consists of…
Path-Fault-Tolerant Approximate Shortest-Path Trees
Annalisa D'Andrea, Mattia D'Emidio, Daniele Frigioni +2
Let be an -nodes non-negatively real-weighted undirected graph. In this paper we show how to enrich a {\em single-source shortest-path tree} (SPT) of with a \emph{…