Graduate Thesis Or Dissertation

 

A comparison of methods for finding Hamiltonian circuits in graphs Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/x346d7325

Descriptions

Attribute NameValues
Creator
Abstract
  • This paper compares three classes of algorithms for finding Hamiltonian circuits in graphs. Two of the classes are exhaustive search procedures and this study finds them to have an exponential dependence on the size of the graph. The third class of algorithms, based on Warnsdorff's rule, is found to be less dependent on the size of the graph but restricted to finding only a single circuit. The effect of density and regularity of the characteristic performance of the algorithms is shown to be minimal.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6670 in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-10-09T20:02:22Z (GMT) No. of bitstreams: 1 DeCurtinsJeffreyL1978.pdf: 300696 bytes, checksum: 8dbd406c16f9669116791d0bee6a0b0b (MD5)
  • description.provenance : Made available in DSpace on 2013-10-09T20:36:38Z (GMT). No. of bitstreams: 1 DeCurtinsJeffreyL1978.pdf: 300696 bytes, checksum: 8dbd406c16f9669116791d0bee6a0b0b (MD5) Previous issue date: 1977-08-12
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-10-09T20:36:38Z (GMT) No. of bitstreams: 1 DeCurtinsJeffreyL1978.pdf: 300696 bytes, checksum: 8dbd406c16f9669116791d0bee6a0b0b (MD5)
  • description.provenance : Submitted by Katy Davis (kdscannerosu@gmail.com) on 2013-10-09T19:35:25Z No. of bitstreams: 1 DeCurtinsJeffreyL1978.pdf: 300696 bytes, checksum: 8dbd406c16f9669116791d0bee6a0b0b (MD5)

Relationships

Parents:

This work has no parents.

Items