Profile minimization on products of graphs
檔案
- 000237997200007.pdf (250.5 KB, Adobe PDF)
日期
2006-05-01
類型
系所
期刊名稱
DISCRETE MATHEMATICS
卷期與頁次
第 306 卷第 8-9 期,頁 792–800
ISSN
0012-365X
語言
英文
摘要
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.