2
$\begingroup$

I have a graph named $G$. degree of each node in $G$ is at most $10$. I need to find an algorithm to determine that this graph has any cycle with length less than $20$ with $O(n)$ .

I think it can solve with any theorem related to $Δ(G)$ and cycle in $G$ (but I'm not sure) .

I search it in google and stackoverflow , but I can't find any solution.

  • 0
    @Saeed thanks for your help. I am newbie here and a bit nonfamiliar with these kind of sites. I swear to improve :)2012-04-03

2 Answers 2

2

There are $O(n)$ vertices in $G$, each of which can be an endpoint of at most $10^1+10^2+10^3+\cdots+10^{19}=O(1)$ walks of lengths between $1$ and $19$.

Hence, brute-force checking all of these $O(n)$ walks (e.g. via depth-first search or breadth-first search) will run in $O(n)$ time (albeit with a horribly large implicit constant).

0

The algorithm for finding a short cycle is BFS. The reason why this has runtime $\mathcal{O}(n)$ in your case is the degree bound on the vertices, which yields that $m\le 5n$.

  • 0
    @Saeed: I am not suggesting anything. All I am saying is this answer does not deserve a downvote. Of course, you are free to vote as you please.2012-04-02