Shachar Don-Yehiya, Leshem Choshen, et al.
ACL 2025
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.
Related
Conference paper
Learning Reduced Order Dynamics via Geometric Representations
Imran Nasim, Melanie Weber
SCML 2024
Khalid Abdulla, Andrew Wirth, et al.
ICIAfS 2014
Baihan Lin, Guillermo Cecchi, et al.
IJCAI 2023