Fine-grained complexity for sparse graphs

DOI10.1145/3188745.3188888zbMath1427.68110arXiv1611.07008OpenAlexW2808782544MaRDI QIDQ5230293

Udit Agarwal, Vijaya Ramachandran

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.07008

zbMATH Keywords

graph algorithmssparse graphsminimum weight cyclefine-grained reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Fine-Grained Complexity Theory (Tutorial) ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths

This page was built for publication: Fine-grained complexity for sparse graphs