Shifting Graphs and Their Applications
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3), 423-432
- https://doi.org/10.1145/321958.321962
Abstract
Graphs that in a certain precise sense are rich in sets of vertex-disjoint paths are studied. Bounds are obtained on the minimum number of edges in such graphs, and these are used to deduce nonlinear lower bounds on the computational complexity of shifting, merging, and matching problems.Keywords
This publication has 7 references indexed in Scilit:
- Relations Among Complexity MeasuresJournal of the ACM, 1979
- Lower Bounds on Merging NetworksJournal of the ACM, 1976
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975
- Combinational complexity of some monotone functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Schnelle Multiplikation großer ZahlenComputing, 1971
- On Permutation Switching NetworksBell System Technical Journal, 1968
- A Permutation NetworkJournal of the ACM, 1968