An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
From MaRDI portal
Publication:1180414
DOI10.1007/BF01206357zbMath0743.68076WikidataQ56701656 ScholiaQ56701656MaRDI QIDQ1180414
Publication date: 27 June 1992
Published in: Combinatorica (Search for Journal in Brave)
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