E-viri
PDF
Recenzirano
Odprti dostop
-
Yamamoto, Masaki
Discrete Applied Mathematics, 01/2017, Letnik: 217Journal Article
We consider the time complexity of problems of counting paths and cycles in a graph, respectively. We first show that these two problems are #P-hard. Then, we show an inapproximability result: there is no FPRAS for approximately counting paths and cycles in a graph, respectively unless RP=NP.
