Skip to main content
MathOverflow

Return to Question

fixed the terminology used to state and explain the problem
Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

How to find the spanninga minimal rooted tree that maximize vertices valueswith maximial sum vertex weights?

I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the spanning tree that maximizes the sum of these values and pass throughrooted at vertex (1,1) that maximizes the sum of these values with a minimal number vertices.

The tree do not have to go through all nodes, although the tree can pick a negative vertex so it can pick a positive one.

Edges have no value.

I will appreciate any advice.

How to find the spanning tree that maximize vertices values?

I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the spanning tree that maximizes the sum of these values and pass through vertex (1,1).

The tree do not have to go through all nodes, although the tree can pick a negative vertex so it can pick a positive one.

Edges have no value.

I will appreciate any advice.

How to find a minimal rooted tree with maximial sum vertex weights?

I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the tree rooted at vertex (1,1) that maximizes the sum of these values with a minimal number vertices.

The tree do not have to go through all nodes, although the tree can pick a negative vertex so it can pick a positive one.

Edges have no value.

I will appreciate any advice.

Source Link
Sghat
Sghat
  • 13
  • 2

How to find the spanning tree that maximize vertices values?

I have an undirected grid graph, nxm, where each vertex has a value (positive or negative) and I need to find the spanning tree that maximizes the sum of these values and pass through vertex (1,1).

The tree do not have to go through all nodes, although the tree can pick a negative vertex so it can pick a positive one.

Edges have no value.

I will appreciate any advice.