前几天在家里下载了一个容量高达3．10GB的超大文件，准备从台式机传输到笔记本中，但是当打开QQ传送文件时，却意外的弹出不能发送的提示行（如图1）。真是郁闷之极。虽然Windows Live Messenger传送文件时没有容量方面的限制,但毕竟...前几天在家里下载了一个容量高达3．10GB的超大文件，准备从台式机传输到笔记本中，但是当打开QQ传送文件时，却意外的弹出不能发送的提示行（如图1）。真是郁闷之极。虽然Windows Live Messenger传送文件时没有容量方面的限制,但毕竟微软的服务器在国外,传输速度非常的缓慢,难道我们只能无奈地等待就么？展开更多
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 inter...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.展开更多
文摘前几天在家里下载了一个容量高达3．10GB的超大文件，准备从台式机传输到笔记本中，但是当打开QQ传送文件时，却意外的弹出不能发送的提示行（如图1）。真是郁闷之极。虽然Windows Live Messenger传送文件时没有容量方面的限制,但毕竟微软的服务器在国外,传输速度非常的缓慢,难道我们只能无奈地等待就么？
基金Supported by the Natural Science Foundation of Henan Province（082300460190） Sponsored by Program for Science and Technology Innovation Talents in Universities of Henan Province.
文摘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.
