1
$\begingroup$

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, because we measure the number of vertices (including the legs), not the length. Find an algorithm with time complexity of O(n).

$\endgroup$
1
  • 3
    $\begingroup$ A caterpillar doesn't ordinarily have the "at most four"-constraint. $\endgroup$
    – Pål GD
    Mar 21 at 18:20

1 Answer 1

1
$\begingroup$

Hint: the heaviest caterpillar that can be formed by a path starting at a node and moving strictly downward in the tree (its down-weight) is

  • the down-weight of the heaviest non-leaf child if it exists, plus
  • the number of leaves attached to this node capped at 4, plus
  • 1 for the node itself.

Then the heaviest caterpillar going through a node at its highest point is

  • the down-weight of the heaviest non-leaf child if it exists, plus
  • the down-weight of the second heaviest non-leaf child if it exists, plus
  • the number of leaves attached to this node capped at 4, plus
  • 1 for the node itself.

You can compute both properties inductively using any tree traversal that visits a nodes' children before itself, and get the global maximum by finding the heaviest weight going through any node in the tree.

$\endgroup$

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.