Personal tools
You are here: Home CG seminar 2023 Labeled and Unlabeled Reconfiguration by Compaction
« January 2023 »
January
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Labeled and Unlabeled Reconfiguration by Compaction

Wednesday, February 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

underline

Maarten Löffler, Utrecht University and Tulane University

Abstract:

We consider configurations of (labeled or unlabeled) objects on an integer lattice, and their behaviour under compaction operations: we may think of these as globally pushing all objects with a horizontal or vertical half-plane by one unit, where objects will also push other objects which are in the way. Under this model, the central question is: given two configurations of the same set of objects, is there a sequence of compaction operations that will transform the first configuration into the second. In this talk, we will consider both the characterization of such configuration pairs where the answer is yes, and the computational complexity of answering this question in general as well as in some special cases.
Document Actions