Efficient testing of large graphs
From MaRDI portal
Publication:5932749
DOI10.1007/S004930070001zbMath1052.68096OpenAlexW3008660429WikidataQ105584595 ScholiaQ105584595MaRDI QIDQ5932749
Noga Alon, Michael Krivelevich, 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 (only showing first 100 items - show all)
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
This page was built for publication: Efficient testing of large graphs
