文献

J-GLOBAL ID：202302218981435645   整理番号：23A0406575

半順序集合の弱埋め込み問題に対するパラメータ化アルゴリズム

著者 (3件)： 宮崎怜子 (北大 大学院情報科学院) ,  有村博紀 (北大 大学院情報科学研究院) ,  小林靖明 (北大 大学院情報科学研究院)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 122  号： 294(COMP2022 21-32)  ページ： 40-47 (WEB ONLY)  発行年： 2022年11月29日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 半順序集合の埋め込み問題は,存在一階論理のモデル検査の固定パラメータ容易性と関連する問題であり,埋め込む半順序集合の大きさと埋め込み先の半順序集合の幅をパラメータとして固定パラメータ容易であることがGajarskyらによって示されている(Gajarskyら,Log.Methods Comput.Sci.,2015).本研究では,この埋め込み問題よりも弱い条件での埋め込み問題を考え,その固定パラメータ容易性を議論する.具体的には,与えられたラベル付き半順序集合PからQへの弱埋め込みがあるかどうか判定する問題に対して,Pの大きさとQの幅をパラメータとして考えたときに高速な固定パラメータアルゴリズムを与える.(著者抄録)

シソーラス用語： 写像 ,  *集合論 ,  半順序 ,  *埋込み【写像】 ,  一階論理 ,  モデル検査 ,  *アルゴリズム ,  可試験性
準シソーラス用語： *パラメータ化アルゴリズム ,  固定パラメータトラクタビリティ ,  単射

分類 (2件)： 計算理論  (JB02000A) ,  集合論  (AB10000I)

引用文献 (9件)：

• Simone Bova, Robert Ganian, and Stefan Szeider. “Model Checking Existential Logic on Partially Ordered Sets”. In: ACM Trans. Comput. Log. 17.2 (2016), p. 10. DOI: 10.1145/2814937.
• Manuel Càceres, Massimo Cairo, Brendan Mumey, Romeo Rizzi, and Alexandru I. Tomescu. “Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time”. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022. 2022, pp. 359-376. DOI:10.1137/1.9781611977073.18.
• Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dàniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. DOI:10.1007/978-3-319-21275-3.
• R. P. Dilworth. “A Decomposition Theorem for Partially Ordered Sets”. In: Annals of Mathematics 51.1 (1950), pp. 161-166.
• Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, and Saket Saurabh. “FO Model Checking on Posets of Bounded Width”. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. Ed. by Venkatesan Guruswami. IEEE Computer Society, 2015, pp. 963-974. DOI: 10.1109/FOCS.2015.63.

タイトルに関連する用語 (2件)： 埋め込み ,  パラメータ化アルゴリズム