Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is this homework? –  Louis Apr 2 '12 at 11:09
    
no. it's not homework. –  Divuneh Apr 2 '12 at 11:17
2  
Re-tagged: graph refers to graphs of functions and not to discrete graphs - please, read the tag wiki when you tag. –  Ilya Apr 2 '12 at 11:32
    
thaks . I will read tag wiki next time. –  Divuneh Apr 2 '12 at 11:38
    
Your question in SO was very poor written, Also it doesn't show any effort, so It was not qualified for it, because of that removed, see my meta question about it. –  Saeed Apr 2 '12 at 23:10

2 Answers 2

up vote 2 down vote accepted

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).

share|improve this answer

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$.

share|improve this answer
    
for finding girth of a graph we need to run BFS for any vertex . then for this it has O(n^2) –  Divuneh Apr 2 '12 at 12:02
    
You do not need to run BFS at any of the vertices that you already visited in a previous run. If you ran BFS at a vertex and found no circuit, you have found a connected component without circuit and you can ignore it for the rest of the algorithm. –  Jesko Hüttenhain Apr 2 '12 at 12:22
    
And by ignoring it, I mean you can ignore the entire component, of course. –  Jesko Hüttenhain Apr 2 '12 at 12:28
    
and if we have a cycle bigger than 19 , how can we ignor this component ? –  Divuneh Apr 2 '12 at 12:36
    

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.