Inflatable graph properties and natural property tests

DOI10.1007/978-3-642-22935-0_46MaRDI QIDQ3088125zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Eyal Rozenberg

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_46

Mathematics Subject Classification ID

Graph theory (05C99) Randomized algorithms (68W20)

Recommendations

• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• On testable properties in bounded degree graphs
• Every monotone graph property is testable
• Efficient testing of large graphs

Cites work

• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A new proof of the graph removal lemma
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Efficient testing of large graphs
• Graph limits and parameter testing
• Hierarchy Theorems for Property Testing
• scientific article; zbMATH DE number 2156274 (Why is no real title available?)
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• Inflatable graph properties and natural property tests
• Property testing and its connection to learning and approximation
• Testing subgraphs in large graphs
• Testing versus Estimation of Graph Properties
• Three theorems regarding testing graph properties

Cited in

(2)

• Inflatable graph properties and natural property tests
• Hierarchy theorems for property testing

This page was built for publication: Inflatable graph properties and natural property tests

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