I really liked Rahul's formulation; is it possible to solve a similar problem of finding Minimum number of envelopes (may be to save some stamps) to send all the envelopes with the graph representation? Maybe by using maximum flow to solve "Minimum path cover in directed acyclic graph", or am I missing a point?
On Sep 30, 11:43 am, Gönenç Ercan <gon...@gmail.com> wrote: > 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 <rahulsinga...@gmail.com> 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
