HW Prob #2

[Jim Kaiser]

So, I am a little stuck on this particular problem. I have an algorithm that works in some instances, but can fail when there are cycles in the graph. Part of the problem (for me) is that the algorithm needs to run in linear time, but I have't though of a way to do that when there are cycles (I assume O(|V| + |E|) is okay). What would be a good approach here? 

Jim 

[Joshua Lepinski]

I thought of a way to create an answer with cycles and keep it linear but my issue is knowing if it's the smallest Virtex Cover or not without making it n^2. I first iterated over the virtesis and then after I had finished I iterated over the edges. since that's 2n it's still linear.

On Wed, Jul 25, 2012 at 9:35 AM, Jim Kaiser <jimka...@gmail.com> wrote:

So, I am a little stuck on this particular problem. I have an algorithm that works in some instances, but can fail when there are cycles in the graph. Part of the problem (for me) is that the algorithm needs to run in linear time, but I have't though of a way to do that when there are cycles (I assume O(|V| + |E|) is okay). What would be a good approach here? 

Jim 

--
You received this message because you are subscribed to the Google Groups "BYU CS 312 Summer 2012" group.
To post to this group, send email to byu-cs-3...@googlegroups.com.
To unsubscribe from this group, send email to byu-cs-312-sum...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Christopher Tensmeyer]

Because the input is a tree, there are no cycles.  For a general graph, the minimum vertex cover problem has been shown to be NP complete.  Don't bother looking for a linear time algorithm for that one.

Chris

On Jul 25, 2012 10:35 AM, "Jim Kaiser" <jimka...@gmail.com> wrote:

So, I am a little stuck on this particular problem. I have an algorithm that works in some instances, but can fail when there are cycles in the graph. Part of the problem (for me) is that the algorithm needs to run in linear time, but I have't though of a way to do that when there are cycles (I assume O(|V| + |E|) is okay). What would be a good approach here? 

Jim 

--

[Jim Kaiser]

Thanks for pointing that out. I completely missed the part of the problem that stated that it is a tree! That does make it much easier.