Profile minimization on compositions of graphs
Resource
Journal of Combinatorial Optimization 14 (2-3): 177-190
Journal
Journal of Combinatorial Optimization
Journal Volume
14
Journal Issue
2-3
Pages
177-190
Date Issued
2007
Author(s)
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) = minf∑v∈V(G)max x∈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. © 2007 Springer Science+Business Media, LLC.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
16.pdf
Size
23.4 KB
Format
Adobe PDF
Checksum
(MD5):b1fd5cf98c0524fa180f91654b665814