最短経路の最致命辺問題のパラメータ化複雑性

• Item type: SIG Technical Reports(1)
• 公開日: 2023-05-03
• タイトル: 最短経路の最致命辺問題のパラメータ化複雑性
• タイトル / 言語: en
• タイトル: Parameterized Complexity of Shortest Path Most Vital Edges Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学大学院情報科学研究科;大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Osaka University Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Osaka University Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Osaka University Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Osaka University Graduate School of Information Science and Technology
• 著者名: 芦田, 雄斗; 北村, 直暉; 泉, 泰介; 増澤, 利光
• 著者名(英): Yuto, Ashida; Naoki, Kitamura; Taisuke, Izumi; Toshimitsu, Masuzawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最短経路の最致命辺問題とは，無向グラフ????，???? の 2 頂点 s，t，故障辺数 d が与えられたとき，???? − ???? における ????−???? 間の距離が最大となるようなサイズ ???? の辺集合 ???? を求める問題と定義される．この問題は ????[1]- 困難であることが知られている．本稿では，???? と道幅の両方の和をパラメータとして取ったとしても，同問題が W[1]- 困難であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given an undirected graph ????, vertices ????, ???? of ????,and the number of removal edges ????,the shortest paths most vital edges problem requires us to find the set ???? of ???? edges whose removal maximizes the distance between ???? and ???? in the graph ???? − ????. This problem was shown to be W[1]-hard with respect to parameters ???? and the pathwidth of ????. In this paper， we show that this problem is also W[1]-hard even taking their sum as the parameter.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2023-AL-193, 号 14, p. 1-7, 発行日 2023-05-03
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会