Testing subgraphs in large graphs
From MaRDI portal
Publication:4798173
DOI10.1002/rsa.10056zbMath1027.68095OpenAlexW2161620758WikidataQ105583182 ScholiaQ105583182MaRDI QIDQ4798173
Publication date: 19 March 2003
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10056
Related Items
Testing Odd-Cycle-Freeness in Boolean Functions, A characterization of easily testable induced digraphs and \(k\)-colored graphs, Polynomial removal lemmas for ordered graphs, Fast Property Testing and Metrics for Permutations, Nearly complete graphs decomposable into large induced matchings and their applications, Efficient Removal Lemmas for Matrices, Patterns without a popular difference, The edit distance function of some graphs, On the benefits of adaptivity in property testing of dense graphs, Sunflowers and testing triangle-freeness of functions, Efficient removal lemmas for matrices, Bounds for graph regularity and removal lemmas, Testing linear inequalities of subgraph statistics, On 3‐graphs with no four vertices spanning exactly two edges, Extremal edge polytopes, The removal lemma for tournaments, Minimum degree and the graph removal lemma, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Unavoidable tournaments, The minimum degree removal lemma thresholds, Local-vs-global combinatorics, Prominent examples of flip processes, Easily Testable Graph Properties, Hierarchy theorems for property testing, Unnamed Item, Unnamed Item, A new proof of the graph removal lemma, Introduction to Testing Graph Properties, Colorings with only rainbow arithmetic progressions, Efficient Testing without Efficient Regularity, The number of $4$-cycles and the cyclomatic number of a finite simple graph, Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts, Property Testing of Massively Parametrized Problems – A Survey, Unnamed Item, Hierarchy theorems for testing properties in size-oblivious query complexity, Some remarks on barycentric-sum problems over cyclic groups, Finite field models in arithmetic combinatorics -- ten years on, Triforce and corners, Unnamed Item, Inflatable Graph Properties and Natural Property Tests, On the Average-Case Complexity of Property Testing, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, Estimating parameters associated with monotone properties, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, New Results on Linear Size Distance Preservers, Unnamed Item, Lower bounds for testing triangle-freeness in Boolean functions
Cites Work
