DocumentCode :
1711140
Title :
Bounds on Monotone Switching Networks for Directed Connectivity
Author :
Potechin, Aaron
Author_Institution :
Math. Dept., MIT, Cambridge, MA, USA
fYear :
2010
Firstpage :
553
Lastpage :
562
Abstract :
We prove that any monotone switching network solving directed connectivity on N vertices must have size NΩ(log N).
Keywords :
communication complexity; switching networks; computational complexity; directed connectivity; monotone switching network; Computational complexity; Computational modeling; Knowledge engineering; Labeling; Polynomials; Switches; L; NL; computational complexity; switching networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
Conference_Location :
Las Vegas, NV
ISSN :
0272-5428
Print_ISBN :
978-1-4244-8525-3
Type :
conf
DOI :
10.1109/FOCS.2010.58
Filename :
5671310
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=1711140
بازگشت