Second shortest simple paths in directed graphs: a crossing decomposition and a span-adaptive exact algorithm
Under the APSP conjecture, no algorithm solves the narrow core in O ( m √ n polylog( nC )) time for all polynomially bounded integer costs: the decomposition confines the known hardness of 2-SP to a small, explicitly described class of detours.
A. Sedeño-Noda
· 0 citations