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/69538
Description
Title
Topics in Combinatorial Algorithms
Author(s)
Ramanan, Prakash V.
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
The study of algorithm design is of fundamental importance in Computer Science. The study of algorithms includes the study of efficient data structures. This thesis deals with various aspects of combinatorial algorithms and data structures.
An important class of data structures, k-ary trees, is studied. A pair of k-ary tree traversals is used to assign a permutation of the integers 1,2,(' . . .) to each k-ary tree T. A pair of traversals in a k-ary tree Representation Scheme (k-RS), if it does not assign the same permutation to two distinct k-ary trees. Such pairs of traversals are characterized. Some interesting properties of k-RS are also studied.
The computational complexity of a problem is of universal interest, both to algorithm design, and to an understanding of the nature of computation. New algorithms for the selection problem are presented and analyzed. The performance of these algorithms improve over that of previously known algorithms.
The problem of finding the maximal elements of a set of n elements in E('d) is studied. The complexity of the problem as a function of both n, the number of points in the input set, and m, the number of maximal elements of the set, is studied.
Finally, the aspect of NP-Completeness is considered. There are two main approaches that can be fruitful in dealing with NP-Complete problems. The first one is to find efficient algorithms for some special cases of the problem. This approach is followed for a personnel assignment problem. The general assignment problem is shown to be NP-Complete. Efficient algorithms are presented for some special cases of the problem.
The second approach in dealing with NP-complete problems is to look for heuristic or approximation algorithms. This approach is followed for the one-dimensional bin packing problem. This problem has been studied extensively, and is known to be NP-Complete. New linear-time on-line approximation algorithms are presented for this problem. Their performance is better than that of previously known on-line algorithms. Also, the results extend to orthogonal packings in two dimension.
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.
