3 papers
cs.DS2024
Directed Token Sliding
Niranka Banerjee, Christian Engels, Duc A. Hoang
Reconfiguration problems involve determining whether two given configurations can be transformed into each other under specific rules. The Token Sliding problem asks whether, given…
cs.DS2024
Distance Recoloring
Niranka Banerjee, Christian Engels, Duc A. Hoang
Reconfiguration problems ask whether one feasible solution can be transformed into another by a sequence of local moves while maintaining feasibility throughout. For integers $d \g…
cs.DS2023
Cell-Probe Lower Bound for Accessible Interval Graphs
Sankardeep Chakraborty, Christian Engels, Seungbum Jo +1
We spot a hole in the area of succinct data structures for graph classes from a universe of size at most . Very often, the input graph is labeled by the user in an arbitrary a…