We are given a list of edges between a set of N vertices. There are atmost three edges joining a vertex. We have to arrange all the vertices on a straight line with the positions numbered from 1 to N so that the sum of the length of all the edges is minimized.
The length of an edge a,b is the difference between the positions of vertices 'a' and 'b' on the line. There are atmost 12 vertices. The algorithm should work within the time limit of 1 second.
I have tried solving this problem by trying all the permutations and finding out the total cost of each edge. But this work only for 8 out of the 12 test-cases to the problem. Because in the worst case the total number of operations is proportional to 12! * 18.
The size of N is very small so I think the solution might be similar to trying all the possibilities.
I don't need the complete solution to this problem because I want to try to come up with it myself but only a hint on how can I optimize my algorithm so that it works within the time limit. Thanks.