Contemplations on Testing Graph Properties

DOI10.1007/978-3-642-22670-0_35MaRDI QIDQ3088201zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 19 August 2011

Published in Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2006/555/

zbMATH Keywords

graph propertiesProperty testing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Testing of graph properties
• Introduction to testing graph properties
• Introduction to testing graph properties
• Testing versus Estimation of Graph Properties
• scientific article; zbMATH DE number 1792102
• Non-deterministic graph property testing
• Testing properties of graphs and functions
• Property testing in bounded degree graphs

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• 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 sublinear bipartiteness tester for bounded degree graphs
• Algorithmic and analysis techniques in property testing
• Approximation algorithms for NP-hard problems.
• Efficient testing of large graphs
• Every monotone graph property is testable
• Introduction to testing graph properties
• On the Benefits of Adaptivity in Property Testing of Dense Graphs
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing k-colorability
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing subgraphs in large graphs
• Testing the diameter of graphs
• Testing versus estimation of graph properties
• The complexity of promise problems with applications to public-key cryptography
• Three theorems regarding testing graph properties
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(4)

• The program of the mini-workshop
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
• Polynomial removal lemma for ordered matchings
• The Complexity of Public-Key Cryptography

This page was built for publication: Contemplations on Testing Graph Properties

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