ラインダイグラフの無閉路彩色とフィードバック頂点集合
スポンサーリンク
概要
- 論文の詳細を見る
無閉路彩色とは,隣接する 2 頂点が異なる色で割当てられ,かつどの 2 色で誘導される部分グラフも閉路を持たない頂点彩色である.一方フィードバック頂点集合は,それを削除することにより閉路を持たないような頂点集合をいう.ここでは,有向グラフのある辺彩色がそのラインダイグラフの底グラフに対する無閉路彩色を与えることを示し,ラインダイグラフに関連するグラフのクラス (de Bruijn グラフや Kautz グラフ等) の無閉路彩色問題およびフィードバック頂点集合問題について考察する.
- 2012-09-27
著者
関連論文
- cycle-rooted treeを用いた複数情報の散布について
- バタフライのde Bruijn族のネットワークへの埋め込み
- 2進一般化de Bruijnグラフのフィードバック頂点集合(グラフとネットワーク)
- 関数に基づく集合分割と有向ハイパーグラフ
- 関数に基づく集合分割と有向ハイパーグラフ
- 関数に基づく集合分割とラインダイグラフ
- Isomorphic factorization of the Kronecker product of generalized de Bruijn digraphs (New Developments of Theory of Computation and Algorithms)
- 反復ラインダイグラフの一般化と de Bruijn ダイグラフへの応用
- ラインダイグラフ演算の一般化と同型因子分解
- E-032 楽曲のグラフ表現とその解析手法(自然言語・音声・音楽,一般論文)
- E-044 楽曲のグラフ表現(自然言語・音声・音楽,一般論文)
- ラインダイグラフの無閉路彩色とフィードバック頂点集合