ダウンロード数: 62
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| s00453-021-00921-9.pdf | 532.02 kB | Adobe PDF | 見る/開く |
| タイトル: | Linear-Time Recognition of Double-Threshold Graphs |
| 著者: | Kobayashi, Yusuke    https://orcid.org/0000-0001-9478-7307 (unconfirmed)Okamoto, Yoshio Otachi, Yota Uno, Yushi |
| 著者名の別形: | 小林, 佑輔 |
| キーワード: | Double-threshold graph Bipartite permutation graph Star pairwise compatibility graph |
| 発行日: | Apr-2022 |
| 出版者: | Springer Nature |
| 誌名: | Algorithmica |
| 巻: | 84 |
| 号: | 4 |
| 開始ページ: | 1163 |
| 終了ページ: | 1181 |
| 抄録: | A graph G=(V, E) is a double-threshold graph if there exist a vertex-weight function w:V→ℝ and two real numbers lb, ub ∈ ℝ such that uv ∈ E if and only if lb ≤ w(u)+w(v) ≤ ub. In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in O(n³ m) time, where n and m are the numbers of vertices and edges, respectively. |
| 著作権等: | © The Author(s) 2022 This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. |
| URI: | http://hdl.handle.net/2433/275982 |
| DOI(出版社版): | 10.1007/s00453-021-00921-9 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス
