An asymptotic bound for the complexity of monotone graph properties

DOI10.1007/s00493-010-2485-3zbMath1231.05222OpenAlexW1983880126WikidataQ56701661 ScholiaQ56701661MaRDI QIDQ653841

Eberhard Triesch, Torsten Korneffel

Publication date: 19 December 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-010-2485-3

zbMATH Keywords

prime number theoremsimplicial complexcomplete bipartite graphasymptotic boundmonotone graph propertyevasiveness conjecturegroup of Oliver-typerecognition complexitytopological property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99)

Related Items

Query complexity of tournament solutions

Cites Work

• Unnamed Item
• Unnamed Item
• A lower bound for the recognition of digraph properties
• A topological approach to evasiveness
• Fixed-point sets of group actions on finite acyclic complexes
• On recognizing graph properties from adjacency matrices
• On the recognition complexity of some graph properties
• Evasiveness of Subgraph Containment and Related Properties
• Monotone Bipartite Graph Properties are Evasive
• Some Results on Elusive Graph Properties
• Fixed-Point Theorems for Periodic Transformations

This page was built for publication: An asymptotic bound for the complexity of monotone graph properties