One thing to note is that, this graph is a directed acyclic graph, since by definition there can be no edge from a smaller or equal sized envelope to a large one. In this setting it is possible to find the longest path, by a topological sort and dynamic programming in linear time O(V+E). Funny though If it wasn't "strictly smaller" than finding the longest path would be NP-Complete.
On Sep 28, 9:03 pm, Rahul Singal <[email protected]> wrote: > A possible solution i can think is create a directed graph where each > vertex is a envelope and edges are from a bigger envelope to smaller > envelope ( one which can fit in bigger envelope ) . Now the problem is > reduce to finding longest path in the graph . > > Regards > Rahul -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
