|
|||||
|
|
Profile minimization on compositions of graphs |
|
| Authors: | Yu-Ping Tsao Gerard J. Chang |
| Affiliation: | 1. China University of Technology, Taipei, Taiwan 2. Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 30050, Taiwan 3. Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan 4. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei, 10617, Taiwan 5. National Center for Theoretical Sciences, Taipei Office, Taipei, Taiwan |
| 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\limits_{f}\sum\limits_{v\in V(G)}\max\limits_{x\in N[v]}(f(v)-f(x)),$$ where f runs over all bijections from V(G) to {1,2,…,|V(G)|} and N[v]={v}∪{x∈V(G):xv∈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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |