Graph problem to minimise total distance from all nodes to a source node under constraints.

Revision en1, by dragoneel, 2018-11-10 17:45:34

I was solving some graph problems with dp and bitmasking when a problem crossed my mind. But I'm unable to solve it optimally. I tried brute force considering all possible combinations. Can we form an optimal solution?

The problem goes like this:

SPECIAL node : Can connect upto 10 nodes.

GOOD node: Is only connected to exactly 1 SPECIAL node and no other node.

VALID edge: Has atleast one SPECIAL node.

VALID graph: A connected graph such that every edge is a VALID edge and each node is either a GOOD node or a SPECIAL node.

Given a connected graph with N nodes (including a source node), your task is to:

  1. Delete 0 or more edges such that the graph becomes a VALID graph.
  2. And the sum of distances from all nodes to source node is minimum.
  3. And the number of SPECIAL nodes is minimum possible.

Note:

  1. Graph is undirected.

  2. It is always possible to connect all nodes.

Constraints:

1<N<=30
1<=E<=435
1<=src<=30

Input: N -> total number of nodes

E edges with values: u v w (there is an edge between u and v with length w)

src -> index of source node

Tags #graph, #graphs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English dragoneel 2018-11-12 11:40:30 86
en1 English dragoneel 2018-11-10 17:45:34 1257 Initial revision (published)