WEKO3
アイテム
点容量付き内向木詰込問題の計算複雑度
https://ipsj.ixsq.nii.ac.jp/records/31601
https://ipsj.ixsq.nii.ac.jp/records/316013245bdae-c536-4825-97fb-ec87ba729680
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL08119008.pdf (854.8 kB)
|
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2008-09-05 | |||||||
| タイトル | ||||||||
| タイトル | 点容量付き内向木詰込問題の計算複雑度 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | The Hardness of the Vertex Capacitated Directed-in-Tree Packing Problem | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京大学 | ||||||||
| 著者所属 | ||||||||
| 上智大学 | ||||||||
| 著者所属 | ||||||||
| 名古屋大学 | ||||||||
| 著者所属 | ||||||||
| 南山大学 | ||||||||
| 著者所属 | ||||||||
| 名古屋大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Univiversity of Tokyo | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Sophia Univiversity | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nagoya Univiversity | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nanzan Univiversity | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nagoya Univiversity | ||||||||
| 著者名 |
今堀, 慎治
宮本, 裕一郎
橋本, 英樹
佐々木, 美裕
柳浦睦憲
× 今堀, 慎治 宮本, 裕一郎 橋本, 英樹 佐々木, 美裕 柳浦睦憲
|
|||||||
| 著者名(英) |
Shinji, Imahori
Yuichiro, Miyamoto
Hideki, Hashimoto
Mihiro, Sasaki
Mutsunori, Yagiura
× Shinji, Imahori Yuichiro, Miyamoto Hideki, Hashimoto Mihiro, Sasaki Mutsunori, Yagiura
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本研究では，有向グラフ，根，点容量関数，枝消費関数が与えられたとき，根付き全域内向木をいくつ詰め込めるかという問題を扱う．枝消費関数によって根付き全域内向木の各点における消費が決まる．制約は，各点において，根付き内向木の消費の合計が点容量を超えないことである．この問題を点容量付き内向木詰込問題とよぶことにする．この問題は，センサーネットワークの研究における最も重要な問題である，ネットワークライフタイム問題の1つである．本研究では，グラフが非巡回的な場合，消費関数が距離に依存する場合，などにおける点容量付き内向木詰込問題の計算複雑度を明らかにした． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this paper, we deal with a vertex capacitated arborescence packing problem. The input consists of a directed graph, a root vertex, a vertex capacity function and edge consumption functions. The problem is to find the maximum number of rooted arborescences such that the total consumption of arborescences at each vertex does not exceed the capacity of the vertex. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We reveal the computational complexity of the problem in several cases; e.g., the given graph is acyclic or not, the instance is metric dependent. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 2008, 号 84(2008-AL-119), p. 57-62, 発行日 2008-09-05 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
