A Lower Bound for the Complexity of Monotone Graph Properties

DOI10.1137/120888703zbMath1267.68169OpenAlexW2024979825WikidataQ56701666 ScholiaQ56701666MaRDI QIDQ5300493

Robert Scheidweiler, Eberhard Triesch

Publication date: 27 June 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/120888703

zbMATH Keywords

evasivenessgraph propertiesdecision tree complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99)

Related Items (3)

A lower bound for metric 1-median selection ⋮ Elusive properties of infinite graphs ⋮ Evasive properties of sparse graphs and some linear equations in primes

This page was built for publication: A Lower Bound for the Complexity of Monotone Graph Properties