Speaker: Francis Lau The University of Hong Kong
Time: 2007-03-13 14:30-2007-03-13 15:30
Venue: FIT Building, Tsinghua University
Download: Click!

Abstract:

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) 
 

Short Bio: