Vertex Ordering Problems in Directed Graph Streams

DOI10.1137/1.9781611975994.109MaRDI QIDQ5146890zbMATH OpenOpenAlexFDO

Authors Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova

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/2105.08215

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(12)

• scientific article; zbMATH DE number 1560506 (Why is no real title available?)
• Vertex ordering with optimal number of adjacent predecessors
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Streaming approximation resistance of every ordering CSP
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• On the communication complexity of finding a king in a tournament
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• New algorithms and lower bounds for streaming tournaments
• Parameterized streaming algorithms for topological sorting
• Constructing long paths in graph streams
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: Vertex Ordering Problems in Directed Graph Streams

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