Re: help on constructing a tree with a mixed criterion

Sorry, the description of the objective is a little bit inacurate. The
actual objective
is to minimize the cost with the format
(1-p)*c_1 + p*c_2,
where c_1 is the sum of the shortest paths from each vertex to the
root
of the tree; and c_2 is the sum of the link weights in the tree.

Obviously, c_1 is lower bounded by the cost of the shortest path tree
(SPT)
in the graph and c_2 is lower bounded by the cost of the minimum
spanning
tree (MST) in the graph.

Thanks,
Cloud


Yecloud wrote:
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: Christians are polluting the Earth with their damn Christmas Trees
    ... Liberals are polluting the earth just by existing! ... Add the cost of electricity to light these trees and the ... Green Tree Envy? ... carbon dioxide, the main heat-trapping emission from human activities. ...
    (alt.politics.bush)
  • A (psossibly) fast, novel search table technique
    ... the cost of function g is data dependent. ... sort of a tree that is sort of a trie. ... For people who think lists we create a list that looks something ... r per read and a hashing cost h per read. ...
    (comp.programming)
  • Re: A (psossibly) fast, novel search table technique
    ... the cost of function g is data dependent. ... sort of a tree that is sort of a trie. ... For people who think lists we create a list that looks something ... r per read and a hashing cost h per read. ...
    (comp.programming)
  • Re: help on constructing a tree with a mixed criterion
    ... of the tree; and c_2 is the sum of the link weights in the tree. ... c_1 is lower bounded by the cost of the shortest path tree ... tree in the graph. ... minimum spanning tree (MST) in graph G, ...
    (comp.theory)
  • Re: How much for a pine tree?
    ... My home owners insurance has a 1k deductible with replacement cost. ... The tree was split from at least half way up to ... Unless it is an actual emergency that it is now imminently in danger of falling and doing additional damage to the residence and/or other property or persons, that's the sequence I would follow, too. ...
    (alt.home.repair)