Joseph Douglas (Joe) HORTON


Address :

Tel :
Fax :
office :
email :

Faculty of Computer Science,
University of New Brunswick
P.O. Box 4400, Fredericton,

(506) 447-3336
(506) 453-3566
E12c, Head Hall

Present Research Activities

Research Interests:Design and analysis of algorithms, graph theory, combinatorics, automated reasoning, network scheduling, complexity .... My most recent research interest is the Simulation Of Consciousness In Artifical Life : the SOCIAL project. Here is the tech-report which I wrote to start the project. I now (2011) have three graduate students working on it.

Topics for CS4997: An incomplete list 2010:

Clause trees: Work with Bruce Spencer. We have developed a new data structure for automated reasoning, the clause tree. Many old algorithms for automated reasoning become easier to understand when viewed as manipulating clause trees. Moreover new tighter algorithms can be defined. The method is useful in solving any problem to which automated reasoning can be applied, from an improved automated theorem proving tool to aid mathematicians (probable), to helping prove programs correct (a long shot). It may be beneficial in proving the security levels of computer systems.

An introduction to clause trees is given in our 1997 paper in Artificial Intelligence. Some details about how to implement them are given in our 2000 paper in the Journal of Automated Reasoning. Implementation seems to be a big problem; we do not have a good efficient implementation.

Complexity:I have a incomplete paper using clause trees. The main results so far are:

The ambitious goal is to show that the size of the smallest proof using extended resolution is exponential (or not).

Haplotype determination: My most recent paper is joint work with my colleague Patricia Evans, and her doctoral student Duong Doan. We have a fast implemented algorithm to determine the haplotypes given the genotype data for the members of an extended family of dyploid individuals. There are many ways in which this research can be extended.

Cycle bases: I have had several results on finding the minimum cycle bases of graphs. The directed case problem has also been considered, but I think that the extension to directed graphs should be done differently than what is in the literature.
Other Research Interests

My original field of research was combinatorial design, an area in which I rarely publish anymore. Three of my papers were published in 1991 in this area.

After completing my Ph.D., I became very interested in graph theory. I found the first known non-hamilton bipartite cubic graph, which was called the Horton graph in the textbook by Bondy and Murty, and the first hypotraceable graph. Perhaps my best work in this area was with Izak Bouwer on symmetric graphs. The joint work with my masters student Kyriakos Kilakos on minimum edge dominating sets is cited more often.

After coming to UNB in 1981, I became interested in Algorithm Analysis. The most important result here, and the paper that has generated the most citations for me, has been the discovery of a polynomial-time algorithm to find the shortest cycle basis of graph. This result has applications in many areas of Mathematics, Engineering and the Sciences.

The other paper of mine that has generated a large number of citations was a partial solution to an old combinatorial geometry problem. I constructed an infinite set of points in the plane in which any set of seven points that formed a convex 7-gon must contain other points inside the 7-gon. This set of points is now often called the horton set.
Selected Publications

Teaching Activities
Non-Professional Activities
Other Research Activities

UNB Homepage 
CS Homepage

Last Revision: Nov. 15, 2011.