グラフのサム数に対する上下界について
スポンサーリンク
概要
- 論文の詳細を見る
単純無向グラフGは次のような点のラベリングLを持つときサムグラフ (sum graph) と呼ばれる. どの点vにも異なる正整数L (v) が割り当てられ, 2点の間u, vに辺が張られているのは, L (w)=L(u)+L(v) なるラベルを持つ点wが存在するときに限る. このようなラベリングは, サムグラフラベリングと呼ばれる. サムグラフラベリングを持つには少なくとも1つ孤立点を含むことが必要であるが, グラフH=(V, E) のサム数とは, サムグラフラベリングを持つためにHに追加しなければならない孤立点の最小数と定義される. 本論文では, グラフH=(V, E) のサム数の上界, 下界を評価する. 特に, グラフの点数n=|V|, 辺数m=|E|を固定したとき, サム数の平均値は少なくともm-3n(logn)/(log((2^^n)/m))-n-1であることを示す (ただし、グラフは名前付きの点集合V上でm本の辺を選ぶ方法で生成される).
- 社団法人電子情報通信学会の論文
- 1998-01-21
著者
関連論文
- 格子型光波網におけるパス割り当て問題に関する考察
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- フローゲームの凸性について(ゲーム理論(2))
- マトロイド上の最小基ゲーム
- ある種の平面有向ネットワークの多品種流問題について(計算アルゴリズムと計算量の基礎理論)
- 最小容量カットアルゴリズムのプログラムによる効率の良い実現法
- 多重グラフにおける(λ+1)-カット
- 無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
- グラフ上の搬送スケジューリング問題の計算の複雑さについて(スケジューリング(2))
- グラフ上の搬送スケジューリング問題の計算の複雑さについて
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)
- T-混合カットにおける領域間連結度の性質(グラフ・ネットワーク(5))
- 最小カット問題の簡潔かつ構成的な証明
- 平面グラフにおける辺遊離操作と辺連結度増大問題について
- 組合せ最適化ゲーム
- 反復ラインダイグラフの深さの浅い独立全域木
- グラフのサム数に対する上下界について
- 格子型光波ネットワークの再構成アルゴリズムについて
- 光波ネットワークのノード再配置アルゴリズムについて
- 双方向マンハッタン・ストリート・ネットワークの網再構成について