Profile minimization on compositions 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 epsilon V(G)) max(x epsilon 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 epsilon V(G): xv epsilon E(G)}. This is equivalent to the interval graph completion problem, which is to find a super-graph of a graph G with as few number of edges as possible. The purpose of this paper is to study the profiles of compositions of two graphs.