A randomized embedding algorithm for trees

DOI10.1007/s00493-010-2422-5zbMath1231.05274MaRDI QIDQ555509

Jan Vondrák, Benjamin Sudakov

Publication date: 22 July 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-010-2422-5

zbMATH Keywords

randomized algorithm; \(C_4\)-free graphs; \(K_{s,t}\)-free graphs; embedding a tree to a graph; graphs of fixed girth

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

05D40: Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)

05C81: Random walks on graphs