About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
Shifting Graphs and Their Applications
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.