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

DOI10.1007/BF01206357zbMath0743.68076WikidataQ56701656 ScholiaQ56701656MaRDI QIDQ1180414

Péter Hajnal

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 (5)

Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ On packing bipartite graphs ⋮ On the Bollobás–Eldridge Conjecture for Bipartite Graphs ⋮ Complexity measures and decision tree complexity: a survey. ⋮ On the bipartite graph packing problem

Cites Work

• Unnamed Item
• Edge disjoint placement of graphs
• A topological approach to evasiveness
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• Subgraphs of graphs. I
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

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