2026-10-08T15:23:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24267 2025-11-12T12:39:38Z ddc:004 open_access

On the Complexity of Minimising the Moving Distance for Dispersing Objects Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Intersection graphs Optimisation Graph modification We study Geometric Graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We first show an O(n log n)-time algorithm that minimises the total moving distance to disperse unit intervals. This algorithm is applied to render a given unit interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. We next show that GGED becomes strongly NP-hard when rendering a weighted interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. Lastly, we prove that minimising the maximum moving distance for rendering a unit disk graph edgeless is strongly NP-hard over the L₁ and L₂ distances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolás Honorato-Droguett and Kazuhiro Kurita and Tesshu Hanaka and Hirotaka Ono 2025 Is Part Of LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WADS.2025.36 urn:nbn:de:0030-drops-242673 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode