2024-03-29T00:48:12Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001451142023-04-27T10:00:04Z01164:02592:07834:08333
二部グラフ中に含まれる弦二部誘導グラフの列挙Enumeration Algorithm for Chordal Induced Bipartite Graphs of a Bipartite Graphjpnhttp://id.nii.ac.jp/1001/00145081/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=145114&item_no=1&attribute_id=1&file_no=1Copyright (c) 2015 by the Information Processing Society of Japan北海道大学大学院情報科学研究科北海道大学大学院情報科学研究科国立情報学研究所九州工業大学大学院情報工学研究院和佐, 州洋有村, 博紀宇野, 毅明平田, 耕一本稿では,弦二部誘導グラフの列挙問題を考察する.二部グラフ B が弦二部グラフであるとは,B に含まれる長さが 6 以上の任意のサイクル C に対して,C 上で隣り合わない 2 頂点の間に,少なくともひとつの辺があるときをいう.主結果として,与えられた二部グラフに含まれるすべての弦二部誘導グラフを,もれなく重複なく出力する多項式遅延列挙アルゴリズムを与える.In this paper, we study an enumeration problem for chordal induced bipartite graphs of a bipartite graph. A bipartite graph B is bipartite chordal if for any cycle C in B whose length is more than four, there exists at least one edge between two vertices that are not adjacent on C. As the main result, we develop a polynomial delay algorithm that enumerates all chordal induced bipartite graphs in a given bipartite graph.AN1009593X研究報告アルゴリズム(AL)2015-AL-1545182015-09-212188-85662015-09-11