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

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

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

This page was built for publication: An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties