Profile minimization on compositions of graphs
檔案
- 000248864800008.pdf (384.6 KB, Adobe PDF)
日期
2007-10-01
系所
期刊名稱
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷期與頁次
第 14 卷第 2-3 期,頁 177–190
ISSN
1382-6905
語言
英文
摘要
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.