Improved upper and lower bound techniques for monotone switching networks for directed connectivity

2013/02/15 by Potechin, Aaron
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI)

paper · doi:10.48550/arxiv.1302.3726

Abstract

In this paper, we analyze the monotone space of complexity of directed connectivity for a large class of input graphs G using the switching network model. The upper and lower bounds we obtain are a significant generalization of previous results and the proofs involve several completely new techniques and ideas.

Related

• Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks
• Bounds on monotone switching networks for directed connectivity
• Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees
• Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
• Improved Monotone Circuit Depth Upper Bound for Directed Graph Reachability