Testing Triangle-Freeness in General Graphs

DOI10.1137/07067917XzbMath1163.68018OpenAlexW1965645254MaRDI QIDQ3629476

Dana Ron, Tali Kaufman, Noga Alon, Michael Krivelevich

Publication date: 27 May 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/07067917x

zbMATH Keywords

Cayley graphsapproximation algorithmsrandomized algorithmsproperty testingtriangle-freenesssubgraph-freeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (7)

Faster Property Testers in a Variation of the Bounded Degree Model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimizing the two-round Even-Mansour cipher ⋮ Fast distributed algorithms for testing graph properties ⋮ Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

This page was built for publication: Testing Triangle-Freeness in General Graphs