| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-01-26 11:10 Edge Load Factor Balancing 問題と既知のNP完全問題との関連について ○春日 輝・山田正史・篠宮紀彦（創価大）  CAS2016-83 ICTSSL2016-37 |
|
| 抄録 | （和） | 本稿では，ネットワークフロー最適化問題の一つとして提案してきた Edge Load factor Balancing (ELB)問題に関して，既知のNP完全問題である Directed Two-commodity Integral Flow (DTIF)問題と対比させることによって性質を分析した．ELB問題は，あるネットワークにおいて，フロー量と辺の容量から定義される負荷率を平滑化するように各フローの経路を求める問題として定式化している．また，ELB問題に制限を与えた場合について，DTIF問題からの還元可能性と，複雑性クラスについて考察する． |
| （英） | This paper analyzes the property of Edge Load factor Balancing (ELB) problem, which is one of network flow optimization problems by comparing it with a well-known NP-complete problem, Directed Two-commodity Integral Flow (DTIF) problem. The ELB problem is formulated as a problem to find a set of paths that smooth edge load factor defined as the ratio of the amount of flows to a capacity of an edge. The complexity class of the restricted ELB problem is discussed based on the reducibility to the DTIF problem. | |
| キーワード | （和） | ネットワークフロー / 負荷分散 / NP 困難 / グラフ理論 / / / / |
| （英） | network flow / load balancing / NP-hard / graph theory / / / / | |
| 文献情報 | 信学技報, vol. 116, no. 421, CAS2016-83, pp. 33-36, 2017年1月. | |
| 資料番号 | CAS2016-83 | |
| 発行日 | 2017-01-19 (CAS, ICTSSL) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2016-83 ICTSSL2016-37 |
|
| 研究会情報 | |
| 研究会 | CAS ICTSSL |
| 開催期間 | 2017-01-26 - 2017-01-27 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 学生セッション、一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | CAS |
| 会議コード | 2017-01-CAS-ICTSSL |
| 本文の言語 | 日本語 |
| タイトル（和） | Edge Load Factor Balancing 問題と既知のNP完全問題との関連について |
| サブタイトル（和） | |
| タイトル（英） | On Relevance between an Edge Load Factor Balancing Problem and the Conventional NP-complete Problems |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ネットワークフロー / network flow |
| キーワード(2)（和/英） | 負荷分散 / load balancing |
| キーワード(3)（和/英） | NP 困難 / NP-hard |
| キーワード(4)（和/英） | グラフ理論 / graph theory |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 春日 輝 / Hikaru Kasuga / カスガ ヒカル |
| 第1著者 所属（和/英） | 創価大学 (略称： 創価大) Soka University (略称： Soka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山田 正史 / Masashi Yamada / ヤマダ マサシ |
| 第2著者 所属（和/英） | 創価大学 (略称： 創価大) Soka University (略称： Soka Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 篠宮 紀彦 / Norihiko Shinomiya / シノミヤ ノリヒコ |
| 第3著者 所属（和/英） | 創価大学 (略称： 創価大) Soka University (略称： Soka Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2017-01-26 11:10:00 |
| 発表時間 | 20分 |
| 申込先研究会 | CAS |
| 資料番号 | CAS2016-83, ICTSSL2016-37 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.421(CAS), no.422(ICTSSL) |
| ページ範囲 | pp.33-36 |
| ページ数 | 4 |
| 発行日 | 2017-01-19 (CAS, ICTSSL) |
[研究会発表申込システムのトップページに戻る]