文献

J-GLOBAL ID：201302274034428597   整理番号：13A0070705

ラインダイグラフの無閉路彩色とフィードバック頂点集合

Acyclic coloring and feedback vertex set of a line digraph

著者 (1件)： 河合博之 (函館工高専)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2012  号： 4  ページ： ROMBUNNO.AL-141,NO.3  発行年： 2012年12月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 無閉路彩色とは,隣接する2頂点が異なる色で割当てられ,かつどの2色で誘導される部分グラフも閉路を持たない頂点彩色である。一方フィードバック頂点集合は,それを削除することにより閉路を持たないような頂点集合をいう。ここでは,有向グラフのある辺彩色がそのラインダイグラフの底グラフに対する無閉路彩色を与えることを示し,ラインダイグラフに関連するグラフのクラス(de BruijnグラフやKautzグラフ等)の無閉路彩色問題およびフィードバック頂点集合問題について考察する。(著者抄録)

シソーラス用語： *彩色問題 ,  閉路 ,  有向グラフ ,  グラフ理論 ,  フィードバック ,  頂点 ,  端部 ,  グラフ ,  集合 ,  *NP困難 ,  アルゴリズム
準シソーラス用語： de Bruijnグラフ ,  Kautzグラフ ,  フィードバック頂点集合 ,  ラインダイグラフ ,  底グラフ ,  辺 ,  *無閉路彩色

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： ダイグラフ ,  閉路 ,  彩色 ,  フィードバック頂点集合