An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties

DOI10.1007/BF01375470zbMath0743.68077MaRDI QIDQ1180407

Valerie King

Publication date: 27 June 1992

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

complexity of graph properties

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

Related Items

An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties

Cites Work

• Edge disjoint placement of graphs
• A topological approach to evasiveness
• On recognizing graph properties from adjacency matrices
• On the theory of graphs