help on constructing a tree with a mixed criterion

Hi,

Sorry for crossing-post.

I meet a problem on constructing a tree with a mixed criterion on an
undirected graph.
The problem is:

Given an undirected graph G(V, E) and a parameter 0<= p <=1, how
to construct a tree T which minimizes the cost with the format
(1-p)*c_SPT + p*c_MST,
where c_SPT is the cost of the shortest path tree (SPT) and c_MST is
the cost of the
minimum spanning tree (MST) in graph G, respectively. Assume that the
edges are assigned
the same weights in SPT and MST.

I would like to know,
(1) As constructing MST and SPT both are in complexity P, is this
problem also in P?
(2) If the problem is in P, is there any algorithm in any reference on
it?
(3) If the problem is in NP, is there any approximate available in the
literature?

Thanks,
Cloud

.

Relevant Pages

  • Re: Phylogenetic question for John Harshman
    ... I mean useful for constructing a phylogenetic ... this car" is *not* useful for constructing a phylogenetic tree. ... mean when you wrote "A plug that works in this car"? ...
    (talk.origins)
  • Re: Phylogenetic question for John Harshman
    ... I mean useful for constructing a phylogenetic ... this car" is *not* useful for constructing a phylogenetic tree. ... Sigh all you like. ... informative traits because they're not a requirement for any ...
    (talk.origins)
  • Re: about tree
    ... beginers of c writes: ... i want a program for constructing a tree in C. ... And also i wish to traverse the tree.pls write a program for it ...
    (comp.lang.c)
  • help on graph algorithms - constructing a tree with a mixed criterion
    ... undirected graph. ... to construct a tree T which minimizes the cost with the format ... minimum spanning tree (MST) in graph G, ... As constructing MST and SPT both are in complexity P, ...
    (sci.math)
  • Re: HTML Parser
    ... > screenshot, I can see that it is event-based. ... it leaves me with the job of constructing ... > and filling all the data for the object tree I need to have. ... Speed wise, it's way snappy.. ...
    (borland.public.delphi.thirdpartytools.general)
Loading