CS Theses & Dissertations 1973

For 1973 graduation dates (in alphabetical order by last name):

The Application of Interactive Graphics and Pattern Recognition to the Reduction of Map Outlines
Clement, Andrew
URI : http://hdl.handle.net/2429/33113
Degree : Master of Science – MSc
Graduation Date : 1973-05

On the Efficiency of Clique Detection in Graphs
Dixon, Anthony Hunter
URI : http://hdl.handle.net/2429/31952
Degree : Doctor of Philosophy – PhD
Graduation Date : 1973-11

This thesis examines the devices employed by various algorithms to search for maximal complete subgraphs in graphs. Also known as cliques, in Chapter 1 these subgraphs are seen to play an important role in graph theory, information retrieval, Sociometry, logic design, and computational complexity. The enumeration of cliques using the Harary-Rcss, Bonner, Peay, and Bron-Kerbosch algorithms is discussed in Chapter 2. The Reduced Redundancy algorithm is introduced, and the performance of the five procedures is assessed using an alternative approach to empirical testing. Each of the algorithms is shown to generate a "derivation tree" for a given graph whose size can be used as a measure of its efficiency. In Chapter 3, the possibility of exploiting vertex similarity is examined with a view to reducing the size of the derivation tree. As a consequence, algorithms are proposed for finding non-similar cliques. The concept of "complete subgraph equivalence" of vertices is introduced to develop a means for expressing the cliques of a graph as the Cartesian product of vertex subsets. An algorithm for detecting the existence of a clique of order k in a certain class of k-partite graphs in polynomial time is proposed in Chapter 4. This class consists of all graphs reducible by the algorithm to k-partite graphs having at most two vertices per block of degree greater than 0. This algorithm is shown to provide an efficient heuristic which can be used in a procedure for determining whether a well-formed formula is a tautology. The thesis is concluded with an empirical analysis of the techniques employed by the enumeration algorithms of Chapter 2. In addition, the efficiency of the Clique Detection algorithm is compared with that of the Reduced Redundancy algorithm.

An Interactive Debugging Package for LISP/MTS
Friedman, Paul
URI : http://hdl.handle.net/2429/32661
Degree : Master of Science – MSc
Graduation Date : 1973-11

A Procedual Approach to Constructions in Euclidean Geometry
Funt, Brian V.
URI : http://hdl.handle.net/2429/32666
Degree : Master of Science – MSc
Graduation Date : 1973-11

The Games of Pentominoes
Kuttner, Michael
URI : http://hdl.handle.net/2429/32697
Degree : Master of Science – MSc
Graduation Date : 1973-05

A Machine Independent Implementation of LOGO
Manis, Vincent S.
URI : http://hdl.handle.net/2429/32925
Degree : Master of Science – MSc
Graduation Date : 1973-11

An Interactive Graphical Program for Specification and Application of WEB Rewriting Rules
Ng, William P.H.
URI : http://hdl.handle.net/2429/33212
Degree : Master of Science – MSc
Graduation Date : 1973-11

Construction of LR(k) Parsers with Application to ALGOL 68
Ramer, David Robert
URI : http://hdl.handle.net/2429/33244
Degree : Master of Science – MSc
Graduation Date : 1973-11

Mode Checking in ALGOL 68
Thomson, John D.
URI : http://hdl.handle.net/2429/32642
Degree : Master of Science – MSc
Graduation Date : 1973-11

GIDS: A Geographical Information System
Yan, Joel Zachary
URI : http://hdl.handle.net/2429/32774
Degree : Master of Science – MSc
Graduation Date : 1973-11



Find us on Twitter

a place of mind, The University of British Columbia

 

ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
General: help@cs.ubc.ca
Undergrad program: undergrad-info@cs.ubc.ca
Graduate program: grad-info@cs.ubc.ca

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia