0
$\begingroup$

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum number of security guards so that the entire museum is guarded. A guard placed in a room can guard that room, its parent room, and its direct child rooms. It is a standard binary tree, and using DFS for bottom-up traversal is expected. Worst case time and space complexity is to be expressed.

I thought traversing as post order and looking whether a node has a parent and having at least one child to assign a guard to it, but it also adds extra guards. Should we also check if a node is guarded etc or is there a better way without it since we traverse bottom to up?

$\endgroup$

1 Answer 1

1
$\begingroup$

This looks like the dominating set problem, but in a tree.

If the tree has two nodes or more, note that it is never interesting to put a guard in a leaf, because putting the guard in its parent will cover more rooms. Conversely, since you need a guard to check the leaf room, you need to put a guard either in the leaf or in its parent.

This gives the idea of an algorithm: using a DFS traversal in post-order, for each node, if it is uncovered, put a guard in its parent. The idea is that after putting a guard in the parent of a leaf (as stated above) and deleting covered nodes, this creates new leaves and you can apply it recursively (note that this can disconnect the tree, but it is not a problem).

$\endgroup$
4
  • $\begingroup$ when do I delete them and will I do a search from beginning? Or why do I delete them, since I won't go back to that node. $\endgroup$
    – mark
    Mar 16 at 16:08
  • $\begingroup$ Sorry, I didn't understand your comment. $\endgroup$
    – Nathaniel
    Mar 16 at 17:59
  • $\begingroup$ May you elaborate further, after deleting the nodes how do I search recursively? $\endgroup$
    – mark
    Mar 16 at 20:27
  • $\begingroup$ That's up to you to make it work, I already gave the idea. $\endgroup$
    – Nathaniel
    Mar 16 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.