Efficient testing of large graphs
From MaRDI portal
Publication:5932749
DOI10.1007/s004930070001zbMath1052.68096OpenAlexW3008660429WikidataQ105584595 ScholiaQ105584595MaRDI QIDQ5932749
Noga Alon, Michael Krivelevich, Mario Szegedy, Eldar Fischer
Publication date: 13 June 2001
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930070001
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A unified view of graph regularity via matrix decompositions, Hypergraph regularity and random sampling, Ramsey numbers of large books, The cycle of length four is strictly \(F\)-Turán-good, Faster Property Testers in a Variation of the Bounded Degree Model, A further extension of Rödl's theorem, Local-vs-global combinatorics, Approximate consistency for transformations on words and trees, Paths of length three are \(K_{r+1}\)-Turán-good, Structured Codes of Graphs, Popular progression differences in vector spaces II, Additive combinatorics and graph theory, Testing graphs against an unknown distribution, Testing Odd-Cycle-Freeness in Boolean Functions, An adaptivity hierarchy theorem for property testing, On the strength of comparisons in property testing, A characterization of easily testable induced digraphs and \(k\)-colored graphs, Polynomial removal lemmas for ordered graphs, Induced arithmetic removal: complexity 1 patterns over finite fields, Perfect Graphs of Fixed Density: Counting and Homogeneous Sets, Additive approximation for edge-deletion problems, On the Interplay Between Strong Regularity and Graph Densification, Efficient Removal Lemmas for Matrices, On the density of a graph and its blowup, The edit distance function of some graphs, On the benefits of adaptivity in property testing of dense graphs, Efficient removal lemmas for matrices, Testing Linear-Invariant Properties, Bounds for graph regularity and removal lemmas, Flexible Models for Testing Graph Properties, Testing linear inequalities of subgraph statistics, On 3‐graphs with no four vertices spanning exactly two edges, Indistinguishability and First-Order Logic, The removal lemma for tournaments, Seeding with Costly Network Information, Unnamed Item, Easily Testable Graph Properties, Comparing the strength of query types in property testing: the case of \(k\)-colorability, Hierarchy theorems for property testing, Unnamed Item, Universality of Graphs with Few Triangles and Anti-Triangles, Testable and untestable classes of first-order formulae, Algorithmic Aspects of Property Testing in the Dense Graphs Model, Limits of kernel operators and the spectral regularity lemma, Introduction to Testing Graph Properties, Regularity lemmas in a Banach space setting, Extremal results in sparse pseudorandom graphs, Strong forms of stability from flag algebra calculations, Testing Eulerianity and connectivity in directed sparse graphs, Distribution-free connectivity testing for sparse graphs, Hyperfinite graphings and combinatorial optimization, Efficient Testing without Efficient Regularity, \(H\)-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, The maximum edit distance from hereditary graph properties, Deterministic vs non-deterministic graph property testing, A sparse regular approximation lemma, Testing Euclidean Spanners, Hierarchy Theorems for Property Testing, Testing of matrix-poset properties, Extrema of graph eigenvalues, Property testing of regular tree languages, Non-Deterministic Graph Property Testing, Minimum Number ofk-Cliques in Graphs with Bounded Independence Number, A separation theorem in property testing, Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Measuring instance difficulty for combinatorial optimization problems, Unnamed Item, Testing permutation properties through subpermutations, Testing hypergraph colorability, Sublinear-time Algorithms, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, The number of graphs with large forbidden subgraphs, Sublinear time algorithms in the theory of groups and semigroups., Generalizations of the removal lemma, Testability and repair of hereditary hypergraph properties, A note on permutation regularity, Two-sided error proximity oblivious testing, Testing subgraphs in directed graphs, Many \(T\) copies in \(H\)-free graphs, Testing Graph Blow-Up, Testing Graph Blow-Up, Maximizing five-cycles in \(K_r\)-free graphs, Arithmetic progressions, different regularity lemmas and removal lemmas, Functions that have read-once branching programs of quadratic size are not necessarily testable, Inflatable Graph Properties and Natural Property Tests, Introduction to Testing Graph Properties, Contemplations on Testing Graph Properties, Minimizing the number of 5-cycles in graphs with given edge-density, The Induced Removal Lemma in Sparse Graphs, Every Set in P Is Strongly Testable Under a Suitable Encoding, Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits, Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal, A unified framework for testing linear‐invariant properties, Relational Properties Expressible with One Universal Quantifier Are Testable, On the Query Complexity of Estimating the Distance to Hereditary Graph Properties, Estimating parameters associated with monotone properties, Sharp bounds for decomposing graphs into edges and triangles, A large lower bound on the query complexity of a simple Boolean function, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Large Book-Cycle Ramsey Numbers, Unnamed Item, An explicit construction of graphs of bounded degree that are far from being Hamiltonian, Every Monotone 3-Graph Property is Testable, Lower bounds for testing triangle-freeness in Boolean functions
