scientific article; zbMATH DE number 7758318
From MaRDI portal
Publication:6084359
DOI10.4230/lipics.approx/random.2020.16arXiv1905.01644MaRDI QIDQ6084359
Hendrik Fichtenberger, Pan Peng, Artur Czumaj, Christian Sohler
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/1905.01644
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Every minor-closed property of sparse graphs is testable
- An adaptivity hierarchy theorem for property testing
- Dynamic graph stream algorithms in \(o(n)\) space
- Structural results on matching estimation with applications to streaming
- Every Property of Hyperfinite Graphs Is Testable
- On Proximity-Oblivious Testing
- Property testing and its connection to learning and approximation
- Maximum Matching in Semi-streaming with Few Passes
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Testing Triangle-Freeness in General Graphs
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Three theorems regarding testing graph properties
- Testing the diameter of graphs
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Tight Bounds for Testing Bipartiteness in General Graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Parameterized Testability
- Testable bounded degree graph properties are random order streamable
- The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
- Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
- Approximate Maximum Matching in Random Streams
- Vertex Ordering Problems in Directed Graph Streams
- Testing Forest-Isomorphism in the Adjacency List Model
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
- Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
- Relating two property testing models for bounded degree directed graphs
- Introduction to Property Testing
- Approximating matching size from random streams
- Planar Graphs: Random Walks and Bipartiteness Testing
- Property testing in bounded degree graphs
This page was built for publication:
