scientific article
From MaRDI portal
Publication:3694708
zbMath0575.68064MaRDI QIDQ3694708
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
exponential lower boundsdirected acyclic graphperfect matchingsHamiltonian circuit functionsn-argument boolean functionnumber of non-sink nodesrestricted boolean networks
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)
Related Items
A simple function that requires exponential size read-once branching programs, On the hierarchy of nondeterministic branching k-programs, Entropy of contact circuits and lower bounds on their complexity, Neither reading few bits twice nor reading illegally helps much, Almost \(k\)-wise independence and hard Boolean functions., Lower bounds for depth-restricted branching programs, Lower bounds on the complexity of real-time branching programs, On the size of binary decision diagrams representing Boolean functions, A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs, On oblivious branching programs of linear length, Lower bounds for linearly transformed OBDDs and FBDDs
