Inflatable Graph Properties and Natural Property Tests

DOI10.1007/978-3-642-22935-0_46zbMath1343.68295OpenAlexW175013254MaRDI QIDQ3088125

Eyal Rozenberg, Eldar Fischer

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)

Related Items

Hierarchy theorems for property testing ⋮ Inflatable Graph Properties and Natural Property Tests

Cites Work

• Unnamed Item
• Unnamed Item
• A new proof of the graph removal lemma
• Graph limits and parameter testing
• Inflatable Graph Properties and Natural Property Tests
• Property testing and its connection to learning and approximation
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Hierarchy Theorems for Property Testing
• Three theorems regarding testing graph properties
• Testing subgraphs in large graphs
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Testing versus Estimation of Graph Properties
• Efficient testing of large graphs