Estimating graph parameters from random order streams

zbMATH Open1403.68363arXiv1711.04881MaRDI QIDQ4608052FDOQ4608052

Authors: Pan Peng, Christian Sohler 

Publication date: 15 March 2018

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

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

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)

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
• Title not available (Why is that?)
• (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)