QQ客服 官方微博 反馈留言

	Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
	Wang, Rui ; Lau, Francis C. M. ; Zhao, Yingchao
	2010-05-06 ; 2010-05-06
关键词	regular graph hamiltonicity consecutive ones NP-completeness Mathematics, Applied
中文摘要	We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A + 1, where A is the adjacency matrix of G, 0 is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G) >= 5 has a Hamiltonian circuit if and only if the matrix A + 1 can be permuted on rows such that each column has at most (or exactly) k - 1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k - 1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A + 1 can be permuted on rows to have at most (or exactly) k - I linear blocks per column. Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k = 1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265); Flammini et a]. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k >= 2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem 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. (C) 2007 Elsevier B.V. All rights reserved.
语种	英语 ; 英语
出版者	ELSEVIER SCIENCE BV ; AMSTERDAM ; PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
内容类型	期刊论文
源URL	[http://hdl.handle.net/123456789/10109]
专题	清华大学
推荐引用方式 GB/T 7714	Wang, Rui,Lau, Francis C. M.,Zhao, Yingchao. Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices[J],2010, 2010.
APA	Wang, Rui,Lau, Francis C. M.,&Zhao, Yingchao.(2010).Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices..
MLA	Wang, Rui,et al."Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices".(2010).

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。