Testing triangle-freeness in general graphs

DOI10.1145/1109557.1109589zbMath1192.68465OpenAlexW4251034921MaRDI QIDQ3581490

Noga Alon, Ron Dana, Tali Kaufman, Michael Krivelevich

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109589

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (7)

Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles ⋮ Tight security for key-alternating ciphers with correlated sub-keys ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Introduction to Testing Graph Properties ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Introduction to Testing Graph Properties

This page was built for publication: Testing triangle-freeness in general graphs