Graduate Thesis Or Dissertation
 

Uniform Hamiltonian touring sequences

Public Deposited

Downloadable Content

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

Descriptions

Attribute NameValues
Creator
Abstract
  • 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 Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
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

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details KinionPaulA1982.pdf 2017-08-23 Public Download