Asymptotic and computational complexity of algorithms and program performance

MaRDI QIDQ6858396zbMATH OpenFDO

Authors O. A. Slavin

Publication date 13 February 2026

Published in Vestnik Yuzhno-Ural'skogo Gosudarstvennogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie (Search for Journal in Brave)

zbMATH Keywords

asymptotic complexitycentral processorcomputational complexitycomputing platformperformancerandom access memory

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Cites work

• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Faster all-pairs shortest paths via circuit complexity
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2221981 (Why is no real title available?)
• Introduction to algorithms.
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Popular conjectures imply strong lower bounds for dynamic problems
• Sketching as a tool for numerical linear algebra
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails

This page was built for publication: Asymptotic and computational complexity of algorithms and program performance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858396)