Uniform Hamiltonian touring sequences Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/pv63g378c

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Sequential machines uniquely determine directed graphs. A path in a sequential machine may be specified by a starting state and an input sequence. A uniform Hamiltonian touring sequence (UHTS) is an input sequence that specifies a Hamiltonian path regardless of the starting state. We present a polynomial time algorithm that determines the existence of a UHTS for a linear sequential machine (LSM) defined over the prime field Z[subscript]p. The problem of whether or not a general graph contains a Hamiltonian path is known to be NP-complete. If we restrict ourselves to directed graphs defined by LSM's then there is a Hamiltonian path if and only if the digraph is strongly connected. This condition is polynomial time testable by determining the rank of the controllability matrix. We show that strong connectedness is not sufficient to guarantee the existence of a UHTS.
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 : Made available in DSpace on 2013-08-26T19:47:12Z (GMT). No. of bitstreams: 1 KinionPaulA1982.pdf: 403272 bytes, checksum: 5b6abbf4579240c73d0053ea173cf90c (MD5) Previous issue date: 1982-05-06
  • description.provenance : Submitted by Katy Davis (kdscannerosu@gmail.com) on 2013-08-26T17:36:12Z No. of bitstreams: 1 KinionPaulA1982.pdf: 403272 bytes, checksum: 5b6abbf4579240c73d0053ea173cf90c (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-08-26T19:47:12Z (GMT) No. of bitstreams: 1 KinionPaulA1982.pdf: 403272 bytes, checksum: 5b6abbf4579240c73d0053ea173cf90c (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-08-26T17:54:28Z (GMT) No. of bitstreams: 1 KinionPaulA1982.pdf: 403272 bytes, checksum: 5b6abbf4579240c73d0053ea173cf90c (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items