Testing triangle-freeness in general graphs

DOI10.1145/1109557.1109589MaRDI QIDQ3581490zbMATH OpenOpenAlexFDO

Authors Noga Alon, Tali Kaufman, Michael Krivelevich, Ron Dana

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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cited in

(7)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581490)