1. Kyoto University Research Information Repository
  2. 400　数理解析研究所
  3. 学術雑誌掲載論文等
ダウンロード数: 56

    このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/2433/279146
このアイテムのファイル:
ファイル 記述 サイズフォーマット 
20m1364370.pdf1.41 MBAdobe PDF見る/開く
完全メタデータレコード
DCフィールド値言語
dc.contributor.authorIto, Takehiroen
dc.contributor.authorKakimura, Naonorien
dc.contributor.authorKamiyama, Naoyukien
dc.contributor.authorKobayashi, Yusukeen
dc.contributor.authorOkamoto, Yoshioen
dc.contributor.alternative小林, 佑輔ja
dc.date.accessioned2023-02-07T09:01:00Z-
dc.date.available2023-02-07T09:01:00Z-
dc.date.issued2022-
dc.identifier.urihttp://hdl.handle.net/2433/279146-
dc.description.abstractMotivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.en
dc.language.isoeng-
dc.publisherSociety for Industrial & Applied Mathematics (SIAM)en
dc.rights© 2022, Society for Industrial and Applied Mathematicsen
dc.subjectgraph algorithmsen
dc.subjectmatchingen
dc.subjectcombinatorial reconfigurationen
dc.subjectcombinatorial shortest pathsen
dc.subject05C85en
dc.subject52B05en
dc.titleShortest Reconfiguration of Perfect Matchings via Alternating Cyclesen
dc.typejournal article-
dc.type.niitypeJournal Article-
dc.identifier.jtitleSIAM Journal on Discrete Mathematicsen
dc.identifier.volume36-
dc.identifier.issue2-
dc.identifier.spage1102-
dc.identifier.epage1123-
dc.relation.doi10.1137/20m1364370-
dc.textversionpublisher-
dcterms.accessRightsopen access-
datacite.awardNumber18H04091-
datacite.awardNumber19K11814-
datacite.awardNumber20H05793-
datacite.awardNumber17K00028-
datacite.awardNumber18H05291-
datacite.awardNumber20H05795-
datacite.awardNumber16K16010-
datacite.awardNumber17K19960-
datacite.awardNumber15K00009-
datacite.awardNumber20K11679-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H04091/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19K11814/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05793/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K00028/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H05291/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05795/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16K16010/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K19960/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15K00009/-
datacite.awardNumber.urihttps://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11679/-
dc.identifier.pissn0895-4801-
dc.identifier.eissn1095-7146-
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理論的に困難な問題を現実的な時間で解くアルゴリズムとデータ構造の研究ja
jpcoar.awardTitle迂回の特性を捉えた最短遷移アルゴリズムに関する研究ja
jpcoar.awardTitle計算機科学アプローチによる組合せ遷移の展開：アルゴリズムの自動生成に向けてja
jpcoar.awardTitle組合せ最適化理論を用いたネットワーク解析手法の設計ja
jpcoar.awardTitle巨大グラフとビッグデータ解析の基礎基盤：　理論研究と高速アルゴリズム開発ja
jpcoar.awardTitle数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へja
jpcoar.awardTitle頑健なネットワークの設計に向けた組合せ最適化理論の研究ja
jpcoar.awardTitle準無限スケジューリング問題の分析と応用ja
jpcoar.awardTitle計算幾何学と計算トポロジーが拓く新時代データ解析の理論基盤ja
jpcoar.awardTitleコンピュータは数学者になれるのか？ --大学数学における自動定理証明ja
出現コレクション:学術雑誌掲載論文等

アイテムの簡略レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。