Every monotone graph property is testable

DOI10.1145/1060590.1060611MaRDI QIDQ3581385zbMATH OpenOpenAlexFDO

Authors Noga Alon, Asaf Shapira

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060611

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Every Monotone Graph Property Is Testable
• Every Monotone 3‐Graph Property is Testable
• Efficient testing of large graphs
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A combinatorial characterization of the testable graph properties, it's all about regularity

Cited in

(36)

• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Lower bounds for testing triangle-freeness in Boolean functions
• A combinatorial characterization of the testable graph properties, it's all about regularity
• Testability and repair of hereditary hypergraph properties
• Inflatable graph properties and natural property tests
• Introduction to testing graph properties
• Contemplations on Testing Graph Properties
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Every Monotone 3-Graph Property is Testable
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Every Monotone Graph Property Is Testable
• Three theorems regarding testing graph properties
• scientific article; zbMATH DE number 6846422 (Why is no real title available?)
• Estimating parameters associated with monotone properties
• Every monotone graph property has a sharp threshold
• Deterministic vs non-deterministic graph property testing
• Introduction to testing graph properties
• Estimating parameters associated with monotone properties
• A generalized Turán problem and its applications
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
• Easily testable graph properties
• Every Monotone 3‐Graph Property is Testable
• Quasi-random words and limits of word sequences
• Efficient testing of large graphs
• On the benefits of adaptivity in property testing of dense graphs
• A property tester for tree-likeness of quartet topologies
• Strongly chordal and chordal bipartite graphs are sandwich monotone
• (Quantum) complexity of testing signed graph clusterability
• Posets are easily testable
• A polynomial removal lemma for posets (extended abstract)
• Distribution-free connectivity testing for sparse graphs
• A separation theorem in property testing
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• Generalizations of the removal lemma

This page was built for publication: Every monotone graph property is testable

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