Låt G vara en ansluten graf, och låt V och V ′ två n-element undergrupper av dess vertex set V (G). Tänk dig att vi placerar ett chip på varje del av V och vi vill flytta dem till positionerna V ′ (V och V ′ kan ha gemensamma element). Ett drag definieras som att flytta ett chip från v 1 till v 2 (v 1, v 2 V (G)) på en väg som bildas av kanter av G så att inga mellanliggande hörn är upptagna. Vi ger övre och nedre gränser på antalet drag som är nödvändiga, och analysera den beräkningsmässiga komplexiteten av detta problem under olika antaganden: märkta kontra omärkta marker, godtyckliga grafer jämfört med fallet när grafen är rektangulära (infinita) planar rutnät, etc. Vi bevisar hårdhet och omätbarhet resultat för flera varianter av problemet. Vi ger också en linjär tid algoritm som utför ett optimalt (minimum) antal drag för den omärkta versionen i ett träd, och en konstant-ratio approximation algoritm för den omärkta versionen i en graf. Grafalgoritmen använder trädalgoritmen som subrutin.
Den omärkta versionen av problemet har också studerats i litteraturen REF.
Reconfigurations in graphs and grids
{'venue': 'in: Proc. LATIN ’06 (Latin American Theoretical INformatics conference), Lecture Notes in Computer Science 3887', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}