Testing subgraphs in directed graphs

DOI10.1016/j.jcss.2004.04.008zbMath1084.68087OpenAlexW3030488835MaRDI QIDQ5917574

Noga Alon, Asaf Shapira

Publication date: 18 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2004.04.008

zbMATH Keywords

CoreProperty testingRegularityDirected graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items

Lower bounds for the smallest singular value of structured random matrices, Spanning trees of dense directed graphs, A characterization of easily testable induced digraphs and \(k\)-colored graphs, Polynomial removal lemmas for ordered graphs, Nearly complete graphs decomposable into large induced matchings and their applications, Bounds for graph regularity and removal lemmas, The removal lemma for tournaments, Unavoidable tournaments, A survey on Hamilton cycles in directed graphs, Packing and Covering a Given Directed Graph in a Directed Graph, Unnamed Item, On Multicolor Ramsey Numbers of Triple System Paths of Length 3, On Directed Versions of the Hajnal–Szemerédi Theorem, Hierarchy theorems for property testing, Unnamed Item, Hamilton decompositions of regular expanders: applications, A new proof of the graph removal lemma, A Dirac-Type Result on Hamilton Cycles in Oriented Graphs, Introduction to Testing Graph Properties, An approximate version of Sumner's universal tournament conjecture, Testing Eulerianity and connectivity in directed sparse graphs, Distribution-free connectivity testing for sparse graphs, Colorings with only rainbow arithmetic progressions, On the Query Complexity of Testing Orientations for Being Eulerian, Directed Graphs Without Short Cycles, An analytic approach to sparse hypergraphs: hypergraph removal, On the structure of oriented graphs and digraphs with forbidden tournaments or cycles, Cycles of given length in oriented graphs, Unnamed Item, Hamiltonian degree sequences in digraphs, Green’s Conjecture and Testing Linear Invariant Properties, Hierarchy theorems for testing properties in size-oblivious query complexity, Tournament quasirandomness from local counting, Dependent random choice, Introduction to Testing Graph Properties, A combinatorial proof of the removal lemma for groups, Triangle packings and 1-factors in oriented graphs, Packing and covering directed triangles asymptotically, Monochromatic trees in random tournaments, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, The Erdös-Hajnal Conjecture-A Survey, Lower bounds for testing triangle-freeness in Boolean functions, A degree sequence Hajnal-Szemerédi theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The core of a graph
• Supersaturated graphs and hypergraphs
• The effect of two cycles on the complexity of colourings by directed graphs
• On graphs with small subgraphs of large chromatic number
• Quick approximation to matrices and applications
• Lower bounds of tower type for Szemerédi's uniformity lemma
• On extremal problems of graphs and generalized graphs
• Regular Languages are Testable with a Constant Number of Queries
• Testing k-colorability
• Property testing and its connection to learning and approximation
• Random sampling and approximation of MAX-CSP problems
• Extremal Graphs without Large Forbidden Subgraphs
• The Algorithmic Aspects of the Regularity Lemma
• Three theorems regarding testing graph properties
• Testing satisfiability
• Testing of Clustering
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Robust Characterizations of Polynomials with Applications to Program Testing
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Testing subgraphs in directed graphs
• Efficient testing of large graphs