TY - GEN
T1 - Algorithms for Optimally Shifting Intervals Under Intersection Graph Models
AU - Honorato-Droguett, Nicolás
AU - Kurita, Kazuhiro
AU - Hanaka, Tesshu
AU - Ono, Hirotaka
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
PY - 2025
Y1 - 2025
N2 - We propose a new model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing operations. As a graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. In this paper, we focus on interval graphs as an intersection graph. We give a linear-time algorithm to find the total moving distance for transforming an interval graph into a complete graph. The concept of this algorithm can be applied for (i) transforming a unit square graph into a complete graph over L1 distance and (ii) attaining the existence of a k-clique on unit interval graphs. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.
AB - We propose a new model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing operations. As a graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. In this paper, we focus on interval graphs as an intersection graph. We give a linear-time algorithm to find the total moving distance for transforming an interval graph into a complete graph. The concept of this algorithm can be applied for (i) transforming a unit square graph into a complete graph over L1 distance and (ii) attaining the existence of a k-clique on unit interval graphs. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.
KW - Graph edit distance
KW - Intersection graphs
KW - Optimisation
UR - http://www.scopus.com/inward/record.url?scp=85215313450&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85215313450&partnerID=8YFLogxK
U2 - 10.1007/978-981-97-7752-5_5
DO - 10.1007/978-981-97-7752-5_5
M3 - Conference contribution
AN - SCOPUS:85215313450
SN - 9789819777518
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 66
EP - 78
BT - Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings
A2 - Li, Bo
A2 - Li, Minming
A2 - Sun, Xiaoming
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024
Y2 - 29 July 2024 through 31 July 2024
ER -