Nick Fischer

activity

20232026

collaborators

Showing 2025Show all

2 papers · 1 filter

cs.DS2025

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection

Amir Abboud, Shyan Akmal, Nick Fischer

We present the first truly subcubic, combinatorial algorithm for detecting an induced $4$ -cycle in a graph. The running time is $O (n^{2.84})$ on $n$ -node graphs, thus separating th…

cs.DS2025

All-Pairs Shortest Paths with Few Weights per Node

Amir Abboud, Nick Fischer, Ce Jin +2

We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most $d$ distinct weights on the outgoing edges from every node. For $d = n$ this…