c*****u
发帖数: 530 | 1 想把一个图中包含的所有可能的cycle全部找出来。
想问一下这是不是一个P 问题，有没有什么好的解法。
谢谢 |
a******e
发帖数: 95 | 2 it is exponential.
【在 c*****u 的大作中提到】
: 想把一个图中包含的所有可能的cycle全部找出来。
: 想问一下这是不是一个P 问题，有没有什么好的解法。
: 谢谢
|
m*****r
发帖数: 9 | 3 In my memory, it seems to be P solvable. Anyway, this problem has been well
studied.
【在 a******e 的大作中提到】
: it is exponential.
|
l*****g
发帖数: 49 | 4
What do you mean by "getting all possible cycles"?
It is easy to construct a graph (with n vertices and O(n) edges) such that the
total number of cycles in that graph is exponential in n. So the output size
of your problem is already exponential.
You want to find some succint representations of all cycles?
【在 c*****u 的大作中提到】
: 想把一个图中包含的所有可能的cycle全部找出来。
: 想问一下这是不是一个P 问题，有没有什么好的解法。
: 谢谢
|
c****r
发帖数: 185 | 5 If one wants to find a set of independent cycles, he can do a depth-first
search.
Then each backtrack edge corresponds to an independent cycle.
The total number is m-n+1 where m is the number of edges and n is the number
of vertices.
the
【在 l*****g 的大作中提到】
:
: What do you mean by "getting all possible cycles"?
: It is easy to construct a graph (with n vertices and O(n) edges) such that the
: total number of cycles in that graph is exponential in n. So the output size
: of your problem is already exponential.
: You want to find some succint representations of all cycles?
|
