File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

TitleHamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
Authors
KeywordsConsecutive ones
Hamiltonicity
NP-completeness
Regular graph
Issue Date2007
PublisherElsevier 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?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/89155
ISSN
2015 Impact Factor: 0.722
2015 SCImago Journal Rankings: 0.880
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorWang, Ren_HK
dc.contributor.authorLau, FCMen_HK
dc.contributor.authorZhao, Yen_HK
dc.date.accessioned2010-09-06T09:53:04Z-
dc.date.available2010-09-06T09:53:04Z-
dc.date.issued2007en_HK
dc.identifier.citationDiscrete Applied Mathematics, 2007, v. 155 n. 17, p. 2312-2320en_HK
dc.identifier.issn0166-218Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/89155-
dc.description.abstractWe 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.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/damen_HK
dc.relation.ispartofDiscrete Applied Mathematicsen_HK
dc.rightsDiscrete Applied Mathematics. Copyright © Elsevier BV.en_HK
dc.subjectConsecutive onesen_HK
dc.subjectHamiltonicityen_HK
dc.subjectNP-completenessen_HK
dc.subjectRegular graphen_HK
dc.titleHamiltonicity of regular graphs and blocks of consecutive ones in symmetric matricesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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+Matricesen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.dam.2007.06.009en_HK
dc.identifier.scopuseid_2-s2.0-34648828918en_HK
dc.identifier.hkuros138641en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34648828918&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume155en_HK
dc.identifier.issue17en_HK
dc.identifier.spage2312en_HK
dc.identifier.epage2320en_HK
dc.identifier.isiWOS:000250823100012-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridWang, R=25653261600en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.scopusauthoridZhao, Y=8641943400en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats