文献

J-GLOBAL ID：201802275580760956   整理番号：18A0328229

グラフにおける近似的計数経路とサイクル【Powered by NICT】

Approximately counting paths and cycles in a graph

著者 (1件)： Yamamoto Masaki (Seikei University, Japan)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 217  号： P2  ページ： 381-387  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 計数経路の問題とグラフにおけるサイクルの時間計算量を考察した。最初に,これら二つの問題は#P-困難であることを示した。近似不能性結果:RPはN Pない限りは,グラフにおける経路とサイクルを数える約のFPRAS,それぞれではないを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *グラフ ,  *近似法 ,  時間計算量

著者キーワード (4件)： 近似計数 ,  #P困難 ,  がFPRAS ,  近似不能性

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： グラフ ,  近似 ,  計数 ,  経路 ,  サイクル