Questions tagged [fine-grained-analysis]

Analyzing the asymptotic complexity of problems already known to be polynomial time solvable. Often, conditional lower bounds are used to show that a specific algorithm is asymptotically optimal.

Filter by
Sorted by
Tagged with
4
votes
1answer
72 views

An example where the algorithm of Hopcroft and Karp performs poorly?

I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I ...
4
votes
1answer
48 views

Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...