Open Access. Powered by Scholars. Published by Universities.®
Discrete Mathematics and Combinatorics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- Combinatorics (28)
- Fibonacci numbers (12)
- Combinatorial identities (6)
- Chebyshev polynomials (3)
- Combinatorial proof (3)
-
- Generating Functions (3)
- Proofs (3)
- Rearrangeable Networks (3)
- Asymptotic Enumeration (2)
- Binomial coefficients (2)
- Counting (2)
- Determinants (2)
- Graph theory (2)
- Harmonic numbers (2)
- Involution (2)
- Lucas numbers (2)
- Switching Systems (2)
- Tiling (2)
- Tilings (2)
- Trees (2)
- 2-3-trees (1)
- Alternating sum (1)
- Asymptotic Analysis (1)
- Asymptotic analysis (1)
- Authomorphism rigidity of graphs (1)
- B-trees (1)
- Bijection (1)
- Binomial identity (1)
- Blocking Probability (1)
- Boolean function (1)
Articles 61 - 62 of 62
Full-Text Articles in Discrete Mathematics and Combinatorics
A New Lower Bound For The Number Of Switches In Rearrangeable Networks, Nicholas Pippenger
A New Lower Bound For The Number Of Switches In Rearrangeable Networks, Nicholas Pippenger
All HMC Faculty Publications and Research
For the commonest model of rearrangeable networks with $n$ inputs and $n$ outputs, it is shown that such a network must contain at least $6n \log _6 n + O( n )$ switches. Similar lower bounds for other models are also presented.
Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder
Optimal 2,3-Trees, Nicholas J. Pippenger, Raymond E. Miller, Arnold L. Rosenberg, Lawrence Snyder
All HMC Faculty Publications and Research
The 2,3-trees that are optimal in the sense of having minimal expected number of nodes visited per access are characterized in terms of their “profiles”. The characterization leads directly to a linear-time algorithm for constructing a K-key optimal 2,3-tree for a sorted list of K keys. A number of results are derived that demonstrate how different in structure these optimal 2,3-trees are from their “average” cousins.