CODEWITHSUNDEEP
algorithmgraphgraph-algorithmcombinatorics
tomKPZ
tomKPZ

Reputation: 837

Find an ordering of nodes in a graph that minimizes sum of edge lengths

Input: A connected undirected graph G with n vertices.

Output: A linear ordering of the vertices 0, 1, ..., n - 1 that minimizes

sum(j - i for i in range(n) for j in range(n) if i < j and (i, j) in G).

n may be about 1000000, and the number of edges will be a constant factor larger than n, around 5000000. In a slightly more general problem, the edges may have small positive integer weights. An exact solution is preferred, but not necessary.

One approach could be a variant of bubble sort that swaps elements if it would bring the sum down. But I'm not sure if this algorithm would get stuck in a local minimum.

Upvotes: 0

Views: 207

Answers (1)

collapsar
collapsar

Reputation: 17258

You seem to be tasked with the Minimum Linear Assignment problem. There is a PhD Thesis on that topic available online ( Seitz, Hanna - Contributions to the Minimum Linear Arrangement Problem ) that has an accessible exposition (see pp. 27 ff.).

The problem is NP-hard. The cited resource reports the complexity of the best known algorithm as O(|E| * 2^|V|) (pp. 29 ff.). It also lists classes of graphs for which efficient (polynomial) algorithms are known and discusses approximation schemes.

PS:
Not an expert here, just ran across the problem and the thesis which appears to be a good starting point.

Upvotes: 2

Related Questions