Profile minimization on products of graphs

Abstract

The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined as P(G) = min(f) Sigma(v is an element of V(G)) max(x is an element of N[v]) (f(v) - f(x)), where f runs over all bijections from V (G) to [1, 2,..., vertical bar V(G)vertical bar] and N[v] = [v] boolean OR [x is an element of V(G) : xv is an element of E(G)]. The main result of this paper is to determine the profiles of K-m x K-n, K-s,K-t x K-n and P-m x K-n. (c) 2006 Elsevier B.V. All rights reserved.