Profile minimization on compositions of graphs

檔案

日期

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.

所屬典藏

會議論文
顯示完整詮釋資料 統計資料

引用此條目

Tsao, Y.-P., & Chang, G. J. (2007). Profile minimization on compositions of graphs. JOURNAL OF COMBINATORIAL OPTIMIZATION, 14(2-3), 177–190. https://doi.org/10.1007/s10878-007-9061-9

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/4007