Profile minimization on triangulated triangles (Q1861244): Difference between revisions

Given a graph with \(n\) vertices, the profile minimization problem is to find a one-to-one function \(f\) from the vertex set to the integers \(1,\dots, n\) such that the sum of the differences \(f(v)-\min f(u)\), where \(u\) is a neighbour of \(v\), is minimized. The authors describe a polynomial algorithm to solve the profile minimization problem for triangulated triangles with side length \(d\). A triangulated triangle with side length \(d\) is a graph whose vertices are triples of nonnegative integers summing up to \(d\). Two vertices are adjacent if the corresponding triples agree in one coordinate of the triple and differ by 1 in the other two coordinates.