File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.dam.2007.06.009
- Scopus: eid_2-s2.0-34648828918
- WOS: WOS:000250823100012
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
Title | Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices |
---|---|
Authors | |
Keywords | Consecutive ones Hamiltonicity NP-completeness Regular graph |
Issue Date | 2007 |
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam |
Citation | Discrete Applied Mathematics, 2007, v. 155 n. 17, p. 2312-2320 How to Cite? |
Abstract | 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 + I, where A is the adjacency matrix of G, I 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 + I 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 + I can be permuted on rows to have at most (or exactly) k - 1 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 al. 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. © 2007 Elsevier B.V. All rights reserved. |
Persistent Identifier | http://hdl.handle.net/10722/89155 |
ISSN | 2023 Impact Factor: 1.0 2023 SCImago Journal Rankings: 0.657 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wang, R | en_HK |
dc.contributor.author | Lau, FCM | en_HK |
dc.contributor.author | Zhao, Y | en_HK |
dc.date.accessioned | 2010-09-06T09:53:04Z | - |
dc.date.available | 2010-09-06T09:53:04Z | - |
dc.date.issued | 2007 | en_HK |
dc.identifier.citation | Discrete Applied Mathematics, 2007, v. 155 n. 17, p. 2312-2320 | en_HK |
dc.identifier.issn | 0166-218X | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89155 | - |
dc.description.abstract | 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 + I, where A is the adjacency matrix of G, I 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 + I 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 + I can be permuted on rows to have at most (or exactly) k - 1 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 al. 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. © 2007 Elsevier B.V. All rights reserved. | en_HK |
dc.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/dam | en_HK |
dc.relation.ispartof | Discrete Applied Mathematics | en_HK |
dc.rights | Discrete Applied Mathematics. Copyright © Elsevier BV. | en_HK |
dc.subject | Consecutive ones | en_HK |
dc.subject | Hamiltonicity | en_HK |
dc.subject | NP-completeness | en_HK |
dc.subject | Regular graph | en_HK |
dc.title | Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0166-218X&volume=155&spage=2312&epage=2320&date=2007&atitle=Hamiltonicity+of+Regular+Graphs+and+Blocks+of+Consecutive+Ones+in+Symmetric+Matrices | en_HK |
dc.identifier.email | Lau, FCM:fcmlau@cs.hku.hk | en_HK |
dc.identifier.authority | Lau, FCM=rp00221 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.dam.2007.06.009 | en_HK |
dc.identifier.scopus | eid_2-s2.0-34648828918 | en_HK |
dc.identifier.hkuros | 138641 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-34648828918&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 155 | en_HK |
dc.identifier.issue | 17 | en_HK |
dc.identifier.spage | 2312 | en_HK |
dc.identifier.epage | 2320 | en_HK |
dc.identifier.isi | WOS:000250823100012 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Wang, R=25653261600 | en_HK |
dc.identifier.scopusauthorid | Lau, FCM=7102749723 | en_HK |
dc.identifier.scopusauthorid | Zhao, Y=8641943400 | en_HK |
dc.identifier.issnl | 0166-218X | - |