Publication
Journal of the ACM
Paper

Shifting Graphs and Their Applications

Download paper

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. © 1976, ACM. All rights reserved.

Date

01 Jul 1976

Publication

Journal of the ACM

Authors

Topics

Resources

Share