Browsing by Author "Tsao, Yu-Ping"

Now showing 1 - 1 of 1

Profile minimization on compositions of graphs
(2007-10-01)
Tsao, Yu-Ping
;
Chang, Gerard J.
;
應用數學系
;
Department of Applied Mathematics
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.