Bipartite permutation graphのL(2,1)ラベリング
スポンサーリンク
概要
- 論文の詳細を見る
グラフGのL(2,1)ラベリングとは,Gの頂点集合から非負整数の集合{0,1,…,λ}への写像fであり,u,vが隣接していれば|f(u)-f(v)|≥2,u,v間の距離が2なら|f(u)-f(v)|≥1となるものである.グラフGがL(2,1)ラベリングを持つ最小のλの値をλ(G)と表す.この問題は,無線ネットワークのチャネル割り当て問題をモデル化したものである.本論文では,bipartite permutation graphに対してL(2,1)ラベリングを求める多項式時間アルゴリズムを示す.提案アルゴリズムのラベリングで用いられる最大のラベルは高々λ(G)+1であり,最適に近いラベリングを計算する.
- 一般社団法人情報処理学会の論文
- 2007-09-21
著者
関連論文
- k木における完全独立全域木について
- k木における完全独立全域木について
- とびらの言葉
- 辺に故障のあるバブルソートグラフのhamiltonian laceability
- バブルソートグラフのedge-bipancyclicityとedge-fault-tolerant bipancyclicity
- ハイパーキューブ族のネットワークにおける適応型故障診断について
- Bipartite permutation graphのL(2,1)ラベリング
- 直並列グラフの最小ペア支配集合を求める線形時間アルゴリズム
- 局所完全ダイグラフの独立双方向支配集合問題について
- 完全独立全域木の十分条件について
- A-004 区間グラフの向き付けにおける双方向支配(アルゴリズム,A分野:モデル・アルゴリズム・プログラミング)
- 完全独立全域木の十分条件について