Optimal Meeting Point with Tree Structure of Depth 2

With just the leaves and a central point, the algorithm of OMP-MIN-MAX or OMP-MIN-SUM is pretty straightforward (i.e. tree depth of one). However I'm a little confused as to how I should tackle graphs/trees with an extra set of intermediary nodes (i.e. depth of 2 or more).

Suppose you have set of leaves, possible intermediary vertices, and one possible meeting point that is also part of a set. The leaves must be in the result, however the result can contain any combination of the other two sets.

For example:

Leaves: leaf1, leaf2, leaf3, leaf4

Intermediary possible vertices: vertex1, vertex2, vertex3, vertex4

Possible meeting points: meetingPoint1, meetingPoint2

An example output could be

[`leaf1`, `leaf2`, `leaf3`, `leaf4`]                   |                   |                vertex2                   |                   |             meetingPoint1  

Or

[`leaf1`, `leaf2`]     [`leaf3`, `leaf4`]          |                      |          |                      |          |                      |       vertex2                vertex4           \                   /             \               /               \           /               meetingPoint1    

What is the correct way to go about this?

https://stackoverflow.com/questions/66093312/optimal-meeting-point-with-tree-structure-of-depth-2 February 08, 2021 at 05:31AM