This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69534
Description
Title
Problems in Sorting and Graph Algorithms
Author(s)
Richards, Dana Scott
Issue Date
1984
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
Five disjoint problems are discussed. The first problem concerns the determination of optimal algorithms with respect to a new model for evaluating sorting algorithms. We did an exhaustive search for such algorithms. The second problem concerns a conjecture that every sorting algorithm on some input involves every key in O(log n) comparisons. We give partial results. The third problem concerns finding efficient algorithms for finding cycles of small fixed length in graphs. We give algorithms for general graphs and O(n log n) algorithms for cycles of length 5 or 6 in planar graphs. The fourth problem concerns the NP-completeness of a wire-routing problem. Specifically, the problem asks for vertex-disjoint paths connecting pairs of points in certain planar graphs. The fifth problem concerns automata traversing graphs in a myopic fashion. We study several cases and show when this can be done and when it is impossible.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
