scientific article; zbMATH DE number 7758318

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.

zbMATH Keywords

sublinear algorithmsgraph property testinggraph streaming algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

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: