2024-03-29T11:07:05Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000316262023-04-27T10:00:04Z01164:02592:02593:02598
平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けてTowards an extension of the planar graph carving-width algorithm to graphs with few-crossings.jpnhttp://id.nii.ac.jp/1001/00031626/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31626&item_no=1&attribute_id=1&file_no=1Copyright (c) 2008 by the Information Processing Society of Japan明治大学理工学部情報科学科明治大学理工学部情報科学科玉木, 久夫吉武, 由実平面グラフの刻み幅を決定する Seymour と Thomas の「ねずみ捕りアルゴリズム」の正当性証明のひとつの鍵となる補題の新しい証明を与える.この証明は,ねずみ捕りアルゴリズムを平面グラフよりも広いクラスに拡張するための基礎となると期待される.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.AN1009593X情報処理学会研究報告アルゴリズム(AL)200824(2008-AL-117)67742008-03-072009-06-30