Estimating graph parameters from random order streams

MaRDI QIDQ4608052zbMATH OpenFDO

Authors Pan Peng, Christian Sohler

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1711.04881, http://dl.acm.org/citation.cfm?id=3175462

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Dynamic graph stream algorithms in \(o(n)\) space
• Dynamic graph stream algorithms in \(o(n)\) space
• Testable bounded degree graph properties are random order streamable
• Approximating matching size from random streams
• scientific article; zbMATH DE number 1756011

Cited in

(8)

• Dynamic graph stream algorithms in \(o(n)\) space
• Constant-time dynamic weight approximation for minimum spanning forest
• Dynamic graph stream algorithms in \(o(n)\) space
• Simulating random walks on graphs in the streaming model
• Testable bounded degree graph properties are random order streamable
• Best-order streaming model
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond

This page was built for publication: Estimating graph parameters from random order streams

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