準完全有向グラフとその一般化に対するパス幅計算について

• Item type: SIG Technical Reports(1)
• 公開日: 2015-02-24
• タイトル: 準完全有向グラフとその一般化に対するパス幅計算について
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 明治大学
• 著者所属: 学習院大学
• 著者所属: 明治大学
• 著者所属(英): en
• 著者所属(英): Meiji University
• 著者所属(英): en
• 著者所属(英): Gakushuin University
• 著者所属(英): en
• 著者所属(英): Meiji University
• 著者名: 橘内, 謙太; 小林, 靖明; 玉木, 久夫
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 有向グラフ G は，その各頂点 u が 「辺 (u,v) も辺 (v,u) も存在しないような頂点 v≠u の個数は高々 h である」 という性質を満たすとき，h 準完全であるという．0 準完全な有向グラフは準完全有向グラフとして知られ，トーナメントはその特別な場合である．本稿では，n 頂点の h 準完全有向グラフ G と正整数 k が与えられたとき，G のパス幅が k 以下であるかを判定する (h+2k+1)2knO(1) 時間のアルゴリズムを与える．この結果は，Pilipczuk の準完全有向グラフに対する結果を （n に対する依存度の犠牲のもとに） 一般化している．我々のアルゴリズムは劣モジュラシステムにおける線形配置問題に対する Nagamochi のアルゴリズムを有向グラフのパス幅問題に特化し，我々の目的のために適合させたものである．「U を 入次数 （出次数） が k 以下であるような任意の頂点集合とするとき，U∪{v} の入次数 （出次数） が k 以下であるような頂点 v の個数は高々 b である」 という性質を満たす有向グラフに対してこのアルゴリズムの実行時間は b2knO(1) である．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2015-AL-152, 号 3, p. 1-8, 発行日 2015-02-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会