Every monotone graph property is testable
From MaRDI portal
Publication:3581385
DOI10.1145/1060590.1060611zbMath1192.68466OpenAlexW1980424184MaRDI QIDQ3581385
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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)
Related Items
Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, On the benefits of adaptivity in property testing of dense graphs, A property tester for tree-likeness of quartet topologies, Introduction to Testing Graph Properties, Strongly chordal and chordal bipartite graphs are sandwich monotone, Distribution-free connectivity testing for sparse graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, 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, Testability and repair of hereditary hypergraph properties, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Quasi-random words and limits of word sequences, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, Every Monotone 3-Graph Property is Testable, Lower bounds for testing triangle-freeness in Boolean functions
