标题:Hamiltonicity of Regular Graphs and Blocks of Consecutive Ones in Symmetric Matr
演讲人: 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)  
 



人物介绍: