Algorithms for Optimally Shifting Intervals under Intersection Graph Models
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914437815861248 |
|---|---|
| author | Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka |
| author_facet | Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka |
| contents | In well-studied graph modification problems, adding and deleting vertices and edges are used as graph editing operations. We propose a model for graph modification on geometric intersection graphs called Geometric Graph Edit Distance that moves objects as an edit operation. Our results are mainly focused on interval graphs. In particular, we give a linear-time algorithm to find the minimum total moving distance to render an interval graph complete. The approach of this algorithm can be applied for: (i) rendering a unit square graph complete over the $L_1$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16964 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Algorithms for Optimally Shifting Intervals under Intersection Graph Models Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Data Structures and Algorithms In well-studied graph modification problems, adding and deleting vertices and edges are used as graph editing operations. We propose a model for graph modification on geometric intersection graphs called Geometric Graph Edit Distance that moves objects as an edit operation. Our results are mainly focused on interval graphs. In particular, we give a linear-time algorithm to find the minimum total moving distance to render an interval graph complete. The approach of this algorithm can be applied for: (i) rendering a unit square graph complete over the $L_1$ 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. |
| title | Algorithms for Optimally Shifting Intervals under Intersection Graph Models |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2312.16964 |