Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
From MaRDI portal
Publication:3507528
DOI10.1137/050627915zbMath1141.05073OpenAlexW1965109958WikidataQ57838767 ScholiaQ57838767MaRDI QIDQ3507528
Noga Alon, Ilan Newman, Eldar Fischer
Publication date: 19 June 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/050627915
Extremal problems in graph theory (05C35) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items
Structure and regularity for subsets of groups with finite VC-dimension, Property testing of the Boolean and binary rank, Ramsey properties of algebraic graphs and hypergraphs, Nondegenerate spheres in four dimensions, Efficient Removal Lemmas for Matrices, Efficient removal lemmas for matrices, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Bounds for graph regularity and removal lemmas, The removal lemma for tournaments, Minimum degree and the graph removal lemma, The structure of almost all graphs in a hereditary property, Local-vs-global combinatorics, Algorithmic Aspects of Property Testing in the Dense Graphs Model, Regular partitions of gentle graphs, Efficient Testing without Efficient Regularity, Testing of matrix-poset properties, Earthmover Resilience and Testing in Ordered Structures, On finite sets of small tripling or small alternation in arbitrary groups, The Entropy of Random-Free Graphons and Properties, Quantitative structure of stable sets in arbitrary finite groups, Large Homogeneous Submatrices, DOMINATION AND REGULARITY
