Interesting algorithm...need insights..
hi all,
Suppose I have a connected graph G(V,E). |V|=n. Every edge in G is
already labelled as either 'A' or 'B'.
I need to devise a polynomial time algorithm which given an integer
'm' ( 1 <= m <= n-1)as input will
either
1) returns a spanning tree with m number of 'A' labelled edges and
(n-1-m) number of 'B' labelled edges.
OR
2) reports correctly that no such tree exists.
Prove that your algorithm works.
I have been trying hard...any ideas or insight is appreciated...
.
Relevant Pages
- hi guys...need insight into this interesting algorithm..Repost
... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
(sci.math) - hi guys...need insight into this interesting algorithm..Repost
... Suppose I have a connected graph G. ... I need to devise a polynomial time algorithm which given an integer ... returns a spanning tree with m number of 'A' labelled edges and ...
(sci.math) - Re: Why isnt NP simply "not polynomial"?
... Why can't NP be defined as the class of decision problems ... It is certainly possible to define a class Not-P (I'll use a different ... there is no *known* polynomial time algorithm. ...
(comp.theory) - Re: Distance normalized TSP algorithm
... have not seen it applied to TSP, but I suspect that is mainly because it ... more challenging than that, but perhaps a bit less challenging than ... finding a polynomial time algorithm for an NP-complete problem. ...
(comp.lang.java.programmer) - Re: Aspiring highest-order programmer
... >> active knowledge into dead secrets in such a way that one can never, ... the moment someone comes up with a polynomial time ... > polynomial time algorithm to solve the problem which makes the problem ... Doesn't this fail to answer the question as to the practicality of the ...
(comp.programming) |
|
