平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて

• Item type: SIG Technical Reports(1)
• 公開日: 2008-03-07
• タイトル: 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
• タイトル / 言語: en
• タイトル: Towards an extension of the planar graph carving-width algorithm to graphs with few-crossings.
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 明治大学理工学部情報科学科
• 著者所属: 明治大学理工学部情報科学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University
• 著者名: 玉木, 久夫; 吉武, 由実
• 著者名(英): Hisao, Tamaki; Yumi, Yoshitake
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面グラフの刻み幅を決定する Seymour と Thomas の「ねずみ捕りアルゴリズム」の正当性証明のひとつの鍵となる補題の新しい証明を与える．この証明は，ねずみ捕りアルゴリズムを平面グラフよりも広いクラスに拡張するための基礎となると期待される．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We give a new proof of a key lemma in the correctness of proof of the "rat-catching algorighm" of Seymour and Thomas which decides the carving-width of planar graphs. This proof is expected to form a basis for extending the rat-catching algorithm to a broader class of graphs.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 24(2008-AL-117), p. 67-74, 発行日 2008-03-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会