完全多部图的区间图完全化问题

The Interval Graph Completion Problem for the Complete Multipartite Graphs

The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined.