演讲人： Francis Lau The University of Hong Kong
时间： 2007-03-13 14:30-2007-03-13 15:30
地点：FIT Building, Tsinghua University
课件下载：点击下载
内容：

We show that the Hamiltonicity of a regular graph can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of the graph, I the unit matrix, and the blocks can be either linear or circular. For the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation, we prove that it remains NP-complete for every constant k >= 2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row. (This is joint work with Rui Wang) 　
 

个人简介: