ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング


インデックスリンク

インデックスツリー

  • RootNode

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 論文誌(ジャーナル)
  2. Vol.57
  3. No.10

連続型・時間/費用トレードオフ最小全域木問題

https://ipsj.ixsq.nii.ac.jp/records/175056
https://ipsj.ixsq.nii.ac.jp/records/175056
eb75c836-9a73-4619-a3f2-3f0ce4d49a8c
名前 / ファイル ライセンス アクション
IPSJ-JNL5710016.pdf IPSJ-JNL5710016.pdf (474.3 kB)
Copyright (c) 2016 by the Information Processing Society of Japan
オープンアクセス
Item type Journal(1)
公開日 2016-10-15
タイトル
タイトル 連続型・時間/費用トレードオフ最小全域木問題
タイトル
言語 en
タイトル Continuous Time/Cost Tradeoff Minimum Spanning Tree Problem
言語
言語 jpn
キーワード
主題Scheme Other
主題 [一般論文] 時間/費用トレードオフ関係,最小木問題,ラグランジュ緩和,釘付けテスト,分枝限定法
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_6501
資源タイプ journal article
著者所属
防衛大学校情報工学科
著者所属
陸上自衛隊
著者所属(英)
en
Department of Computer Science, National Defense Academy
著者所属(英)
en
Japan Grand Self Defense Force
著者名 片岡, 靖詞

× 片岡, 靖詞

片岡, 靖詞

Search repository
村崎, 暢彦

× 村崎, 暢彦

村崎, 暢彦

Search repository
著者名(英) Seiji, Kataoka

× Seiji, Kataoka

en Seiji, Kataoka

Search repository
Masahiko, Murasaki

× Masahiko, Murasaki

en Masahiko, Murasaki

Search repository
論文抄録
内容記述タイプ Other
内容記述 最小全域木問題は,グラフの各枝に時間などのデータが与えられているとき,総時間を最小化する全域木を求める問題である.本研究では,各枝に与えられた時間が,資金を投入することにより短縮できる場合を考え,限られた資金の中で総時間を最小にする全域木を求める問題を扱う.各枝における時間の短縮は,資金の投入額に応じて連続的かつ線形的に時間短縮ができる場合を想定しているので,この問題を連続型時間/費用トレードオフ最小全域木問題と呼ぶことにする.このような問題設定は,プロジェクトスケジューリングでは,CPMとして古くから知られている扱いやすい問題設定であるが,最小木問題の場合は,線形的に時間短縮ができる場合でもNP困難である.また,解には特徴的な構造を持つことが知られているが,この性質について先行研究とは別の証明を示す.定式化の構造からラグランジュ緩和は2つの独立した扱いやすい問題に分割でき,効果的に上下界値が導出できる.また,この上下界値を利用して釘付けテストを行い,多くの場合において分枝限定法に入る前に最適解が得られることを示す.釘付けテストは枝数が多くなると,時間的負担も増えてくるものの,疎なグラフ,特に平面的グラフにおいては,先行研究よりも優れた結果を得た.
論文抄録(英)
内容記述タイプ Other
内容記述 Given an undirected graph and a parameter such as time on each edge, the minimum spanning tree problem is a problem of finding a spanning tree that minimizes total time. In this study, we consider the case that the time on each edge can be reduced by throwing resource such as extra fare into the edge, and find the minimum total time spanning tree within a total resource constraint. As for the reduction of time for each edge, we assume that it can be continuously and linearly reduced. Therefore, we call the problem the continuous time/cost tradeoff minimum spanning tree problem. This kind of continuous and linear tradeoff relationship is often seen in the subject of project scheduling problems, which has been studied before as CPM and is easily solvable. But in the case of the minimum spanning tree problem, even though the tradeoff relationship is continuous and linear, the problem is known to be NP-hard. Also we prove that the optimal solution has a characteristic structure. These proofs are different from those seen in the past research. Based on our formulation, we show that the Lagrangian relaxation problem is divided into two independent tractable problems. Hence, we succeed in obtaining upper and lower bounds efficiently. By applying these bounds into the pegging test, we show that in many cases optimal solutions are obtained before going forward to the branch-and-bound algorithm. As the number of edges becomes large, the computational burden increases, but our computational results are superior to the results in the past research, especially when the graph is sparse.
書誌レコードID
収録物識別子タイプ NCID
収録物識別子 AN00116647
書誌情報 情報処理学会論文誌

巻 57, 号 10, p. 2260-2271, 発行日 2016-10-15
ISSN
収録物識別子タイプ ISSN
収録物識別子 1882-7764
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-20 06:21:11.441449
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3