scientific article; zbMATH DE number 168429

MaRDI QIDQ4036171zbMATH OpenFDO

Authors Hans Dietmar Gröger

Publication date 16 May 1993

zbMATH Keywords

isomorphism propertieslower boundnon-trivial, monotone graph propertyrandomized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An asymptotic bound for the complexity of monotone graph properties
• A lower bound for the complexity of monotone graph properties
• The monotone complexity of \(k\)-clique on random graphs
• Lower bounds to randomized algorithms for graph properties
• scientific article; zbMATH DE number 1754599
• Improved lower bounds on the randomized complexity of graph properties
• Bounded monochromatic components for random graphs
• On the typical structure of graphs in a monotone property
• scientific article; zbMATH DE number 4204394
• The monoid of the random graph

Cited in

(11)

• An \(\Omega{} (n^{5/4})\) lower bound on the randomized complexity of graph properties
• The monoid of the random graph
• Bounded monochromatic components for random graphs
• No easy puzzles: hardness results for jigsaw puzzles
• Improved lower bounds on the randomized complexity of graph properties
• scientific article; zbMATH DE number 2019628 (Why is no real title available?)
• scientific article; zbMATH DE number 1754599 (Why is no real title available?)
• Monotone Properties of k -Uniform Hypergraphs Are Weakly Evasive
• Measures on monotone properties of graphs
• On the typical structure of graphs in a monotone property
• Lower bounds to randomized algorithms for graph properties

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036171)