混雑度の低い疎なネットワークの設計

Material type: 文書・図像類

Author: 大舘, 陽太

Publisher: -

Publication date: 2013-04-11

Material Format: Digital

Capacity, size, etc.: -

NDC: -

View All

Notes on use

Note (General)：: 混雑度の低い疎なネットワークの設計問題のうち，特に全域木混雑度問題と呼ばれるグラフに対する最適化問題を研究し，計算理論的に難しい場合と易しい場合に対してある種の線引きを行った．また，1990年代から注目されている「固定パラメータ計算量」という計算理論的概念も研究し，いくつかの基準に対して困難な場合と...

Search by Bookstore

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

JAIST Repository
Digital
You can check the holdings of institutions and databases with which Institutional Repositories DataBase(IRDB)(Institutional Repository) is linked at the site of Institutional Repositories DataBase(IRDB)(Institutional Repository).
JAIST Repository

Search by Bookstore

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Digital

Material Type: 文書・図像類
Title: 混雑度の低い疎なネットワークの設計
Author/Editor: 大舘, 陽太
Author Heading: 大舘, 陽太
Publication Date: 2013-04-11
Publication Date (W3CDTF): 2013-04-11
Alternative Title: Designing low-congestion sparse networks
Periodical title: 科学研究費助成事業研究成果報告書
Pages: 1-4
Text Language Code: jpn
Subject Heading: 全域木混雑度問題
グラフアルゴリズム
計算複雑性
Target Audience: 一般
Note (General): 混雑度の低い疎なネットワークの設計問題のうち，特に全域木混雑度問題と呼ばれるグラフに対する最適化問題を研究し，計算理論的に難しい場合と易しい場合に対してある種の線引きを行った．また，1990年代から注目されている「固定パラメータ計算量」という計算理論的概念も研究し，いくつかの基準に対して困難な場合と容易な場合の2分法を与えた．研究結果から，この問題は多くの場合で非常に難しいということが分かったので，発見的手法や近似手法などの研究にも取り組み，部分的な成果を得た． : We studied the problem of designing low-congestion sparse networks. Especially, we studied the computational complexity of an optimization problem on graphs called “the spanning tree congestion problem.” We presented sharp contrasts between hard cases and easy cases. We also investigated the parameterized complexity of the problem and gave some dichotomies for the problem. Our results imply the problem is really hard to solve for most of the cases. Thus we designed some heuristic and approximation algorithm and obtained some partial results.
研究種目：研究活動スタート支援
研究期間：2011～2012
課題番号：23800004
研究者番号：80610196
研究分野：グラフアルゴリズム
科研費の分科・細目：情報学基礎
identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/11374
Access Restrictions: 限定公開
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 北陸先端科学技術大学院大学 : JAIST学術研究成果リポジトリ