Lazy or eager dynamic matching may not be fast

DOI10.1016/j.ipl.2020.105982zbMath1462.68233OpenAlexW3036650104MaRDI QIDQ2203578

N. S. Narayanaswamy, Manas Jyoti Kashyop

Publication date: 7 October 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2020.105982

zbMATH Keywords

lower boundgraph algorithmsdynamic matching

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Finding and counting given length cycles
• Powers of tensors and fast matrix multiplication
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching

This page was built for publication: Lazy or eager dynamic matching may not be fast