An Edit Model and Algorithms for Achieving Properties on Intersection Graphs

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-14
• タイトル: An Edit Model and Algorithms for Achieving Properties on Intersection Graphs
• タイトル / 言語: en
• タイトル: An Edit Model and Algorithms for Achieving Properties on Intersection Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
• 著者所属: Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
• 著者所属: Department of Informatics, Faculty of Information Science and Electrical Engineering, Kyushu University
• 著者所属: Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Faculty of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Informatics, Graduate School of Informatics, Nagoya University
• 著者名: Nicolás, Honorato Droguett; Kazuhiro, Kurita; Tesshu, Hanaka; Hirotaka, Ono
• 著者名(英): Nicolás, Honorato Droguett; Kazuhiro, Kurita; Tesshu, Hanaka; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We propose a new general model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are common graph editing operations. As a new graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. We first 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. We modify the presented model and show that its min-max version is NP-hard for disk graphs over L1 and L2 distance. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We propose a new general model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are common graph editing operations. As a new graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. We first 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. We modify the presented model and show that its min-max version is NP-hard for disk graphs over L1 and L2 distance. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-197, 号 5, p. 1-3, 発行日 2024-03-14
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会