ダウンロード数: 62
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| s00453-021-00921-9.pdf | 532.02 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
| DCフィールド | 値 | 言語 |
|---|---|---|
| dc.contributor.author | Kobayashi, Yusuke | en |
| dc.contributor.author | Okamoto, Yoshio | en |
| dc.contributor.author | Otachi, Yota | en |
| dc.contributor.author | Uno, Yushi | en |
| dc.contributor.alternative | 小林, 佑輔 | ja |
| dc.date.accessioned | 2022-08-25T09:06:22Z | - |
| dc.date.available | 2022-08-25T09:06:22Z | - |
| dc.date.issued | 2022-04 | - |
| dc.identifier.uri | http://hdl.handle.net/2433/275982 | - |
| dc.description.abstract | 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. | en |
| dc.language.iso | eng | - |
| dc.publisher | Springer Nature | en |
| dc.rights | © The Author(s) 2022 | en |
| dc.rights | 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. | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | - |
| dc.subject | Double-threshold graph | en |
| dc.subject | Bipartite permutation graph | en |
| dc.subject | Star pairwise compatibility graph | en |
| dc.title | Linear-Time Recognition of Double-Threshold Graphs | en |
| dc.type | journal article | - |
| dc.type.niitype | Journal Article | - |
| dc.identifier.jtitle | Algorithmica | en |
| dc.identifier.volume | 84 | - |
| dc.identifier.issue | 4 | - |
| dc.identifier.spage | 1163 | - |
| dc.identifier.epage | 1181 | - |
| dc.relation.doi | 10.1007/s00453-021-00921-9 | - |
| dc.textversion | publisher | - |
| dcterms.accessRights | open access | - |
| datacite.awardNumber | 17K00017 | - |
| datacite.awardNumber | 18H04091 | - |
| datacite.awardNumber | 18H05291 | - |
| datacite.awardNumber | 18K11168 | - |
| datacite.awardNumber | 18K11169 | - |
| datacite.awardNumber | 20H05793 | - |
| datacite.awardNumber | 20H05795 | - |
| datacite.awardNumber | 20H05964 | - |
| datacite.awardNumber | 20K11670 | - |
| datacite.awardNumber | 20K11692 | - |
| datacite.awardNumber | 20K20417 | - |
| datacite.awardNumber | 21K11752 | - |
| datacite.awardNumber | 21K11757 | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K00017/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H04091/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H05291/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18K11168/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18K11169/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05793/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05795/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05964/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11670/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11692/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K20417/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K11752/ | - |
| datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K11757/ | - |
| dc.identifier.pissn | 0178-4617 | - |
| dc.identifier.eissn | 1432-0541 | - |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.funderName | 日本学術振興会 | ja |
| jpcoar.awardTitle | 離散最適化に対する固定パラメータアルゴリズムの深化：多項式時間FPTと実用化 | ja |
| jpcoar.awardTitle | 理論的に困難な問題を現実的な時間で解くアルゴリズムとデータ構造の研究 | ja |
| jpcoar.awardTitle | 巨大グラフとビッグデータ解析の基礎基盤：理論研究と高速アルゴリズム開発 | ja |
| jpcoar.awardTitle | 特殊木構造によるFPTアルゴリズム高速化手法の研究 | ja |
| jpcoar.awardTitle | 固定パラメータ困難問題に対する汎用解法の研究 | ja |
| jpcoar.awardTitle | 計算機科学アプローチによる組合せ遷移の展開：アルゴリズムの自動生成に向けて | ja |
| jpcoar.awardTitle | 数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ | ja |
| jpcoar.awardTitle | 大規模離散構造の理解と革新的アルゴリズム基盤の創出 | ja |
| jpcoar.awardTitle | 大規模配位空間の最適化理論：離散構造論の視点を中心にして | ja |
| jpcoar.awardTitle | 組合せ最適化における多面体手法の高度化 | ja |
| jpcoar.awardTitle | 走行税課金による道路インフラ維持管理 --EV化と車両認証のデジタル時代を迎えて-- | ja |
| jpcoar.awardTitle | グラフ構造パラメータ階層の詳細化による精緻なアルゴリズム設計と計算量解析 | ja |
| jpcoar.awardTitle | 数理的パズルやゲームが持つ計算原理の解明とそれらの汎用問題解決手法としての体系化 | ja |
| 出現コレクション: | 学術雑誌掲載論文等 | |
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス
