Institution: | a Department of Computer Science, University of Texas, Austin, TX 78712, USA b Department of Computer Science, Western Michigan University, Kalamazoo, MI 49008, USA |
Abstract: | Given graph G=(V,E) on n vertices, the profile minimization problem is to find a one-to-one function f:V→{1,2,…,n} such that ∑vV(G){f(v)?minxNv] f(x)} is as small as possible, where Nv]={v}{x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle Tl is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles Tl with side-length l. |