クリーク幅の構成表現に対するグラフ分解手法の適用の検討

• Item type: SIG Technical Reports(1)
• 公開日: 2022-03-07
• タイトル: クリーク幅の構成表現に対するグラフ分解手法の適用の検討
• タイトル / 言語: en
• タイトル: Graph decompositions for approximating clique-widths
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): University of Electro-Communications
• 著者名: 鈴木, 絢香
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，クリーク幅の近似値を求める問題に対して，グラフの分解手法を適用した場合の知見を与える．ここでグラフの分解手法の適用とは，クリーク幅を求めたいグラフを小さなグラフに分解して，そのグラフのクリーク幅を求め，小さなグラフから元のグラフのクリーク幅を求める方法である．具体的には，グラフの分解手法としてスプリット分解に着目し，次を明らかにした．(1) スプリット分解を用いて小さく分解したグラフを再び構成する際に，構成表現数が増えないような分解順序の性質を明らかにした．さらにそのような分解順序を導出するアルゴリズムを提案した．(2) スプリット分解を拡張した概念として擬スプリット分解を定義し，スプリット分解で分解できないグラフに対する分解手法を与えた．またモジュール連結度という概念を定義し，グラフを再構成するために追加で必要なラベル数に関して，そのラベル数が少ない分解手法から多い分解手法への順序づけを可能とした．これらの定義を用いてクリーク幅が定まるグラフにまで分解できると仮定した場合の構成表現数を求めた．また，擬スプリット分解とランク幅との関係を考察した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This work studies decomposition methods of graphs for approximating clique-widths. In these methods, clique-width expressions are obtained by decomposing a given graph, obtaining clique-width expressions of the decomposed graphs, and reconstructing the given graph. We focus on split decompositions and show two main results. (1) We prove properties of the decomposition orders that do not increase the number of labels of clique-width expressions and propose an algorithm to compute such a decomposition order. (2) We introduce pseudo-split decompositions by extending split decompositions. They are able to decompose graphs with no split. Then, we define the module connectivity, which allows to select fewer labels that are used to reconstruct a given graph. By using these concepts, we show an upper bound of the number of labels of clique-width expressions under the hypothesis that clique-width expressions of the decomposed graphs can be obtained. We also consider the relation between pseudo-split decompositions and rank-widths.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-187, 号 3, p. 1-6, 発行日 2022-03-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会