✦ LIBER ✦

An improved lower bound on the sensitivity complexity of graph properties

✍ Scribed by Xiaoming Sun

Book ID: 108281748
Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 313 KB
Volume: 412
Category: Article
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2011.02.042

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An Ω(n4/3) lower bound on the randomized

An Ω(n4/3) lower bound on the randomized complexity of graph properties

✍ Péter Hajnal 📂 Article 📅 1991 🏛 Springer-Verlag 🌐 English ⚖ 657 KB

An Ω(n5/4) lower bound on the randomized

An Ω(n5/4) lower bound on the randomized complexity of graph properties

✍ Valerie King 📂 Article 📅 1991 🏛 Springer-Verlag 🌐 English ⚖ 546 KB

On the sensitivity complexity of biparti

On the sensitivity complexity of bipartite graph properties

✍ Gao, Yihan; Mao, Jieming; Sun, Xiaoming; Zuo, Song 📂 Article 📅 2013 🏛 Elsevier Science 🌐 English ⚖ 342 KB

An asymptotic bound for the complexity o

An asymptotic bound for the complexity of monotone graph properties

✍ Torsten Korneffel; Eberhard Triesch 📂 Article 📅 2010 🏛 Springer-Verlag 🌐 English ⚖ 171 KB

An improved lower bound for the time com

An improved lower bound for the time complexity of mutual exclusion

✍ James H. Anderson; Yong-Jik Kim 📂 Article 📅 2002 🏛 Springer-Verlag 🌐 English ⚖ 604 KB

An improved edge bound on the interval n

An improved edge bound on the interval number of a graph

✍ Jeremy R. Spinrad; G. Vijayan; Douglas B. West 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 2 views

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees. A representation of a graph as an intersection graph assigns each vertex a set such that vertices are a