如何在图中找到具有最大可能高度的树？

Question

你应该假设给出了正则图。图不是多重图，也没有自边。我正在寻找上限为 O(n^2)

的算法

Answer 1

具有最大高度的树将包括（从根到叶）G 中的最长 可能路径

在未加权的无向图中寻找最长路径的问题is NP-hard。因此没有 O(n²) 算法来解决它。