Profile minimization on triangulated triangles
type: Item
instance of: scholarly article
title: Profile minimization on triangulated triangles
zbMATH Open document ID: 1019.05053
DOI: 10.1016/S0012-365X(02)00450-8
author: Yuqiang Guan
author: Kenneth L. Williams
published in: Discrete Mathematics
publication date: 2003-03-16T00:00:00Z
review text: 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.
reviewed by: Erwin Pesch
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1882179
zbMATH Keywords: bandwidth
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1882179