Algorithms for Optimally Shifting Intervals Under Intersection Graph Models

Nicolás Honorato-Droguett; Kazuhiro Kurita; Tesshu Hanaka; Hirotaka Ono

doi:10.1007/978-981-97-7752-5_5

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models

Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 L₁ 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.

Original language	English
Title of host publication	Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings
Editors	Bo Li, Minming Li, Xiaoming Sun
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	66-78
Number of pages	13
ISBN (Print)	9789819777518
DOIs	https://doi.org/10.1007/978-981-97-7752-5_5
Publication status	Published - 2025
Event	18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024 - Hong Kong, China Duration: Jul 29 2024 → Jul 31 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14752 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024
Country/Territory	China
City	Hong Kong
Period	7/29/24 → 7/31/24

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-981-97-7752-5_5

Cite this

Honorato-Droguett, N., Kurita, K., Hanaka, T., & Ono, H. (2025). Algorithms for Optimally Shifting Intervals Under Intersection Graph Models. In B. Li, M. Li, & X. Sun (Eds.), Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings (pp. 66-78). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14752 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-97-7752-5_5

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models. / Honorato-Droguett, Nicolás; Kurita, Kazuhiro; Hanaka, Tesshu et al.
Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. ed. / Bo Li; Minming Li; Xiaoming Sun. Springer Science and Business Media Deutschland GmbH, 2025. p. 66-78 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14752 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Honorato-Droguett, N, Kurita, K, Hanaka, T & Ono, H 2025, Algorithms for Optimally Shifting Intervals Under Intersection Graph Models. in B Li, M Li & X Sun (eds), Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14752 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 66-78, 18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024, Hong Kong, China, 7/29/24. https://doi.org/10.1007/978-981-97-7752-5_5

Honorato-Droguett N, Kurita K, Hanaka T, Ono H. Algorithms for Optimally Shifting Intervals Under Intersection Graph Models. In Li B, Li M, Sun X, editors, Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2025. p. 66-78. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-97-7752-5_5

Honorato-Droguett, Nicolás ; Kurita, Kazuhiro ; Hanaka, Tesshu et al. / Algorithms for Optimally Shifting Intervals Under Intersection Graph Models. Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. editor / Bo Li ; Minming Li ; Xiaoming Sun. Springer Science and Business Media Deutschland GmbH, 2025. pp. 66-78 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c3a86c60ca6f47d092e8ca32d8e4be7a,

title = "Algorithms for Optimally Shifting Intervals Under Intersection Graph Models",

abstract = "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.",

keywords = "Graph edit distance, Intersection graphs, Optimisation",

author = "Nicol{\'a}s Honorato-Droguett and Kazuhiro Kurita and Tesshu Hanaka and Hirotaka Ono",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.; 18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024 ; Conference date: 29-07-2024 Through 31-07-2024",

year = "2025",

doi = "10.1007/978-981-97-7752-5_5",

language = "English",

isbn = "9789819777518",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "66--78",

editor = "Bo Li and Minming Li and Xiaoming Sun",

booktitle = "Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings",

address = "Germany",

}

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 -