木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
グラフの k-L(2, 1) -ラベリングとは,頂点への 0 から k までの整数値の割り当てであり,隣接頂点間では少なくとも 2,距離 2 の頂点間では少なくとも 1 の差があるもののことを言う.L(2, 1) -ラベリング問題とは,グラフに対する k-L(2, 1) ラベリングの中で最小の k を求めるものである.この問題は,木幅が 2 のグラフに対してでも NP 困難であることが知られている.一方,多項式時間アルゴリズムは,路や閉路,木といった限られたクラスにしか知られておらず,木に対するアルゴリズムの計算量も 10 年以上 O(Δ4.5n) 時間であった (ただし,Δ はグラフの最大次数,n は木の頂点数).この計算量は最近になって O(min{n1.75, Δ1.5n}) 時間へと改善されたが,線形時間で解けるかどうかは未解決であった.本論文では,これを解決する木の L(2, 1) -ラベリングに対する線形時間アルゴリズムを提案する.
- 一般社団法人情報処理学会の論文
- 2009-11-20
著者
-
小野 廣隆
九州大学大学院システム情報科学研究院
-
小野 廣隆
九州大学
-
宇野 裕之
大阪府立大学理学系研究科
-
石井 利昌
小樽商科大学商学部社会情報学科
-
蓮沼 徹
徳島大学
-
蓮沼 徹
徳島大学総合科学部
-
石井 利昌
小樽商科大学
-
宇野 裕之
大阪府立大学理学系研究科情報数理科学専攻
-
宇野 裕之
大阪府立大学
-
小野 廣隆
九州大学システム情報科学府
関連論文
- 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- 証明書分散問題の近似可能性について
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- Highly connected k-tuple twin dominating sets in iterated line digraphs (通信方式)
- Highly connected k-tuple twin dominating sets in iterated line digraphs (回路とシステム)
- 再構成問題の計算複雑さ
- 点集合間の辺連結度を増大させる問題
- 2-D-19 最長路問題に対する次数2以下の点の除去処理とその分枝限定法での利用(離散最適化)
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 平成20年秋季研究発表会ルポ(情報の窓)
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 局所情報を用いたスケールフリーネットワークの探索
- Investigating Web Structure by Cliques and Stars (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- ウェブグラフ : その性質と利用(OR研究の最前線)
- 2-C-6 最長路問題に対する2連結成分分解にもとづく分枝限定法による厳密解法(グラフ・ネットワーク(1))
- 複数の交叉演算による遺伝的アルゴリズムの改良(2)交叉演算を選択するファジィルールの改良
- 段階的な視界をもつマルチエージェントにおける強化学習について(2)方向による視界の変化について
- 逐次入力を用いた忘却型ファジィ・ニューラルネットワークによるファジィルールの学習
- 量限定子を持つファジィルールの抽出手法の改良
- 複数の交叉演算による遺伝的アルゴリズムの改良
- ファジィ決定木生成法 ファジィC4.5とその改良(その3) : 修正利得のパラメータを節点の深さとデータ数に応じて変化させる方法
- ファジィ索引とその類似データに基づく推論への応用
- ファジィ決定木生成法 ファジィC4.5とその改良(その2) : 節点に応じて修正利得を変化させる方法
- 幾何図形におけるアナロジーへのファジィ理論の応用 : 図形の変化の階層的決定法
- 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ
- 木の(p, q)-全ラベリング問題
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 反復ラインダイグラフにおける高連結k-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
- 反復ラインダイグラフにおける高連結κ-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
- 反復ラインダイグラフにおける高連結κ-組双支配集合(一般,ネットワーク,通信のための信号処理及び一般)
- 孤立クリークおよび孤立スター縮約ウェブグラフにおけるウェブ構造マイニング
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- グラフの最小出次数最大化問題
- 順列制約をみたす模調要求をもつ正モジュラシステムについて
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- 閾グラフの最小辺ランキング全域木について
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- 混合ドミノタイリングの連結性
- ルールの生成法と推論法を変化させる学習の拡張
- 幾何図形におけるアナロジーへのファジィ理論の応用
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- 最小辺ランキング全域木問題について
- On Minimum Edge Ranking Spanning Trees
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
- 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
- 近傍探索の解合流性に基づく並列局所探索法の考察(計算理論とアルゴリズムの新展開)
- ルールの生成法と推論法を変化させる学習の拡張 : 保有するデータ数を制限する場合
- 無向グラフにおける単調な要求関数を持つ辺連結度増大問題
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- k-集合合意問題を解く故障検知器
- 移動物体回収問題
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 故障数制限付きリーダー選挙問題に対する故障検知器
- ホーン理論の内包・外包に対する演繹推論
- センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)
- DNA計算における局所探索法による反応障壁近似計算
- DNA計算における局所探索法による反応障壁近似計算
- 最大出次数を最小化するグラフ有向化について
- ファジィ索引とその類似データ検索への応用
- 量子回路における定数段加算器の設計(計算理論)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- マッチングを用いたパターン形成アルゴリズム
- センサーネットワークにおける省電力高信頼なデータ伝送(計算理論とアルゴリズムの新展開)
- 非同期分散システムにおける故障検知器と故障計数器について(計算理論とアルゴリズムの新展開)
- DNA 分子の濃度と反応速度の関係解析(計算理論とアルゴリズムの新展開)
- 最大支配問題
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- 文書データベースへの効率的な索引付けとその更新に関する研究
- 最小重み負荷分散枝被覆について
- ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- Reconfiguration of List L(2,1)-Labelings in a Graph (コンピュテーション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- RA-002 文字列圧縮を用いたネットワークセキュリティにおけるインシデント検出(アルゴリズムと応用(2),A分野:モデル・アルゴリズム・プログラミング)
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)