I made a mistake while constructing worst case input.
Just ignore it.
On Nov 14, 2007 11:50 AM, hongcheng zhu <[EMAIL PROTECTED]> wrote:
> It looks good.
> Have you done some experiments to test its efficiency?
> Maybe (1) is not such a strong branch-cutting condition as y
; is supposed to save a lot of time.
>
> I originally think this is a dynamic programming algorithm and thanks
> to Lin He who pointed out that there is actually a possibility for (3)
> and suggested it can still be an efficient search algorithm.
>
> Your comments are appreciat
ld be reversed as "work to
> place awesome an is Google"
> The solution should be efficient and shouldn't use any extra memory.
>
> Pl suggest me some solution.
>
> Regards,
> Somesh
>
> >
>
--
Hongcheng Zhu
--~--~-~--~~~---~
;
>Can some provide me hint or solution to the following problem.
>
> If a graph has O(|V|) edges , then show that it can be colored
> with (O|V| ^ 1/2) colors.
>
> Thanks
>
>
> >
>
--
Hongcheng Zhu
--~--~-~--~~~---~--~-
..
>
> I think that the approach for this has to be something like a proof by
> contradiction.
>
>
> On Jul 21, 3:38 am, "hongcheng zhu" <[EMAIL PROTECTED]> wrote:
> > I have a simple proof.
> > Assume existing two different spanning trees, say Ta
I have a simple proof.
Assume existing two different spanning trees, say Ta and Tb.
Let Ea={edges of Ta} Eb={edges of Tb}
Let e be the maximum weighted edge that belongs to either of Ea and Eb but
not both.
Assume e belongs to Ea. We remove e from Ta, and Ta becomes two disjoint
sub-trees Ta1 a
