(r_<11>, r_<12>, r_<22>)-トーナメントの得点列対問題 : 構成アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• Gを性質P(例 : 無向グラフ、有向グラフなど)をもつグラフとし、Sを非負で非減少な整数列とする。規定された次数列問題とは、与えられた数列Sが頂点の次数または出次数となっているようなグラフGが存在するかどうかを判定する問題である。1950年代以降、Pは広く拡張され、ErdosやHararyを代表とする多くの研究者により発展してきた。本稿ではPを以下の(1)(2)を満たす性質とする : (1)Gは2つの重複のない頂点集合A, Bをもつ有向グラフである。(2)Aのすべての頂点対の間には各々r_<11>本の有向辺が存在し、Bのすべての頂点対の間には各々r_<22>本の有向辺が存在し、AとBの頂点のすべての対の間には各々r_<12>本の有向辺が存在する。このときGを(r_<11>, r_<12>, r_<22>)-トーナメント("トーナメント"と略す)という。また、この問題を"トーナメント"の得点列問題(実現可能と略す)という。問題の答えがyesならばSを"トーナメント"の得点列という。近年私たちは、2つの整数列が実現可能かどうかを線形時間で判定するアルゴリズムを提案した。本稿では、実現可能な2つの整数列から"トーナメント"を構成する最適アルゴリズムを提案する。

• 社団法人電子情報通信学会の論文
• 2006-01-04

著者

• 吉村 猛

  早稲田大学

• 高橋 昌也

  福岡工業大学短期大学部:早稲田大学大学院情報生産システム研究科

• 渡邊 孝博

  早稲田大学大学院情報生産システム研究科

• 渡邊 孝博

  早稲田大学大学院 情報生産システム研究科

• 吉村 猛

  早稲田大学大学院情報生産システム研究科

関連論文

• 1.メディア処理における超低消費電力SoC技術(未来を切り拓く最先端VLSIテクノロジー)
• A Partitioning-based Logic Optimization Method for Large Scale Circuits with Boolean Matrix
• 情報ネットワークに関する基礎教育
• Rooted Tree Sequence Problem
• k-Edge-Connected Multigraphical Degree Sequence Problem
• 点部分集合に関する拡大構成問題
• Via数削減による大規模LSIレイアウトの高速DRC手法
• (r_, r_, r_)-トーナメントの得点列対問題 : 構成アルゴリズム
• (r_, r_, r_)-得点列対問題 : 構成可能性の判定
• GAを用いたディジタル回路設計の一手法
• C-12-34 スーパスカラプロセッサの分岐回復の高速化に関する研究(C-12.集積回路,一般セッション)
• D-6-20 Network-on-Chipにおける消費電力を考慮したルーティングの一手法(D-6. コンピュータシステム,一般セッション)
• D-6-19 パケット位置情報を用いたオンチップ・ルータの消費電力削減手法の提案(D-6. コンピュータシステム,一般セッション)
• A-3-12 多層ハイパーグラフを用いた超大規模回路の電圧島の分割問題の解法(A-3. VLSI設計技術,一般セッション)
• A-1-28 FPGAとSoftCoreを用いたチップ・マルチプロセッサの検討(A-1. 回路とシステム,一般セッション)
• C_008 Rip-up IPを用いたカスタマイズ設計環境(C分野:ハードウェア)
• D-6-2 分岐処理の高速化に関する一手法(D-6. コンピュータシステム, 情報・システム1)
• 効率的なFPGA実装を指向したニューラルネットワークのアーキテクチャ
• A general neural network architecture for efficient FPGA-based implementation (VLSI設計技術)
• A-1-32 ピンの時分割多重化を利用したFPGA分割手法(A-1. 回路とシステム, 基礎・境界)
• 物理設計CADとネットワーク算法(プロセス・デバイス・回路シミュレーション及び一般)
• 物理設計CADとネットワーク算法(プロセス・デバイス・回路シミュレーション及び一般)
• RC-002 Reducing Branch Misprediction Penalty in Superscalar Microprocessors by Recovering Critical Misprediction
• C_010 FPGA向大規模回路分割手法に関する研究(C分野:ハードウェア)
• 高集積可能なソフトモジュール向けFixed-Outlineフロアプランナ (第20回 回路とシステム軽井沢ワークショップ論文集) -- (レイアウト)
• LVSの出力情報を活用したVLSI電源配線幅の高速検証システム(ソフトウェア工学)

もっと見る 閉じる

スポンサーリンク