from    
to    
search  

 


Symmetry restoration and quantum Mpemba effects in chaotic andlocalization sy...
Quantum Gases 2024
Stories of Fermions in an Optical Box
Contractive Unitary and Classical Shadow Tomography
报告题目:
Hamiltonicity of Regular Graphs and Blocks of Consecutive Ones in Symmetric Matrices
 报告人:
Prof. Francis Lau
The University of Hong Kong
报告时间:
2007-03-13 14:30
报告地点:
FIT 4-603
主办单位:
清华大学理论计算机科学研究中心
  简介:

 
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)

 

今日相关信息
美国消费者权益保护的法律和案例分析
“入世后的中国”系列活动第一场:伟大的博...
解决民生是政府的最大政绩——对政府工作报...
学术抄袭、司法对策与法律教育的危机
 
同类别相关信息
清华信息科学与技术国家实验室学术沙龙:...
Large Scale Computing in Computatio...
建立云计算解析能力实现大数据安全与智慧
清华论坛第51期:积极应对气候变化 努...
WORKING WITH CHINESE MEDIA, AN ANGL...
学术活动