講演抄録/キーワード |
講演名 |
2021-10-23 16:30
木幅の小さなDAGがランダムな枝長さを持つ場合の最長路長さ分布関数の計算 ○安藤 映(専修大) COMP2021-20 |
抄録 |
(和) |
有向非巡回グラフ(DAG)において最長路問題を考える.
この問題はグラフの枝長さが確定的な値として与えられる場合,
効率的な解法がよく知られている.
しかし,グラフの枝長さが互いに独立で一様分布に従う確率変数で
ある場合は$#P$-困難な問題である.
本稿ではDAG $G=(V,E)$について辺の向きを取り除いたグラフ(基礎グラフ)
の木幅が定数$k$で抑えられる場合について,互いに独立で一様分布に従う確率変数の
枝長さを考える場合に対する決定性近似アルゴリズムを示す.
このアルゴリズムは
$Oleft((3k+2)^2 nleft(frac{(6k+6)mn}{epsilon}right)^{9k^2+15k+6}right)$
時間で完了し,
問題に対する完全多項式時間近似スキーム(FPTAS)である. |
(英) |
Consider the problem of computing the longest path length
in directed acyclic graphs (DAGs).
It is well known that the problem can be solved efficiently
when the edge lengths are static values.
However, if we assume that the edge lengths are the mutually
independent and uniformly distributed random variables,
the problem is known to be $#P$-hard.
Here we present a deterministic approximation algorithm
for the problem.
Given a DAG $G=(V,E)$ and that the treewidth of its underlying
undirected graph is bounded by a
constant $k$, then our algorithm finishes in $Oleft((3k+2)^2 nleft(frac{(6k+6)mn}{epsilon}right)^{9k^2+15k+6}right)$ time.
Our algorithm is a fully polynomial time approximation
scheme (FPTAS). |
キーワード |
(和) |
#P-困難問題 / DAG / 最長路問題 / FPTAS / / / / |
(英) |
#P-hard problem / DAG / longest path problem / FPTAS / / / / |
文献情報 |
信学技報, vol. 121, no. 218, COMP2021-20, pp. 39-46, 2021年10月. |
資料番号 |
COMP2021-20 |
発行日 |
2021-10-16 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2021-20 |