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

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

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

(7)

• Best-order streaming model
• Dynamic graph stream algorithms in \(o(n)\) space
• Dynamic graph stream algorithms in \(o(n)\) space
• Constant-time dynamic weight approximation for minimum spanning forest
• 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
• Testable bounded degree graph properties are random order streamable

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)