Official

G - Net of Net Editorial by DEGwer


The net of \(P\) is obtained by cutting \(P\) open along a spanning tree of \(P\). Thus, for a net \(N\) of \(P\), the followings are equivalent:

  • There is a net of \(N\) that is a path.
  • \(N\) has an Eulerian path.
  • \(N\) has at most two vertex of odd degree.

To compute the maximum weight of such \(N\), we use a dynamic programming algorithm like the \(O(3^n poly(n))\)-time algorithm for the minimum Steiner tree problem. Thus, this algorithm can be solved in \(O(3^n poly(n))\)-time.

Note that, the convex hull of given points can just be computed as follows: For all three points, check whether all remaining points are on the same side of the plain determined by these three points.

posted:
last update: