A Lower Bound on Cycle-Finding in Sparse Digraphs

DOI10.1137/1.9781611975994.178MaRDI QIDQ5146975zbMATH OpenOpenAlexFDO

Authors Xi Chen, Timothy Sun, Timothy W. Randolph, Rocco A. Servedio

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• A Lower Bound on Cycle-Finding in Sparse Digraphs
• scientific article; zbMATH DE number 1670872
• Finding a long directed cycle
• Testing properties of directed graphs: acyclicity and connectivity*
• Finding cycles and trees in sublinear time

Cited in

(4)

• Listing all fixed-length simple cycles in sparse graphs in optimal time
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• An Optimal Lower Bound for the Size of Periodic Digraphs
• A Lower Bound on Cycle-Finding in Sparse Digraphs

This page was built for publication: A Lower Bound on Cycle-Finding in Sparse Digraphs

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