Introduction to testing graph properties

DOI10.1007/978-3-642-22670-0_32zbMATH Open1343.68299OpenAlexW2113337364MaRDI QIDQ3088198FDOQ3088198

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://doi.org/10.1007/978-3-642-22670-0_32

Recommendations

• Introduction to testing graph properties
• A brief introduction to property testing
• scientific article; zbMATH DE number 1857651
• Property testing and its connection to learning and approximation
• The subgraph testing model

zbMATH Keywords

randomized algorithmsgraph propertiesapproximation problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cites Work

• Approximation algorithms for NP-hard problems.
• Testing subgraphs in directed graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Property testing and its connection to learning and approximation
• Title not available (Why is that?)
• Efficient testing of large graphs
• Property testing in bounded degree graphs
• Self-testing/correcting with applications to numerical problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Algorithmic and analysis techniques in property testing
• Computational Complexity
• Title not available (Why is that?)
• MAX-CUT has a randomized approximation scheme in dense graphs
• A combinatorial characterization of the testable graph properties
• The complexity of promise problems with applications to public-key cryptography
• A sublinear bipartiteness tester for bounded degree graphs
• Three theorems regarding testing graph properties
• Approximating average parameters of graphs
• Testing subgraphs in large graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds for sampling algorithms for estimating the average
• Testing the expansion of a graph
• Testing triangle-freeness in general graphs
• Testing the diameter of graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Tight Bounds for Testing Bipartiteness in General Graphs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Hierarchy theorems for property testing
• Approximate hypergraph partitioning and applications
• A separation theorem in property testing
• Local Graph Partitions for Approximation and Testing
• An Expansion Tester for Bounded Degree Graphs
• Testing \(k\)-colorability
• Every monotone graph property is testable
• Testing versus estimation of graph properties
• Tolerant property testing and distance approximation
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• Title not available (Why is that?)
• A brief introduction to property testing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing graph isomorphism
• On the Benefits of Adaptivity in Property Testing of Dense Graphs

Cited In (11)

• Title not available (Why is that?)
• Testing Lipschitz functions on hypergrid domains
• Non-interactive proofs of proximity
• Contemplations on Testing Graph Properties
• Randomness and computation
• Erasures versus errors in local decoding and property testing
• A Brief Introduction to Property Testing
• A brief introduction to property testing
• Introduction to testing graph properties
• Testing list \(H\)-homomorphisms
• Title not available (Why is that?)

This page was built for publication: Introduction to testing graph properties

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