Jonathan Turner is a Senior Professor in the Department of Computer
Science and Engineering, at Washington University.
While no longer a fulltime faculty member, he continues to
work on selected research projects.
His research interests include the design of instruments for
automated longterm monitoring of marine environments,
hyperspectral analysis of seawater,
design and analysis of algorithms and data structures.
He is a Fellow of the IEEE, a Fellow of the ACM and a
member of the National Academy of Engineering.
Current/Recent Projects
 The Optical Phytoplankton Detector (OPD) is a marine spectrophotometer first
developed by the Mote Marine Research Laboratory starting around 2005.
It performs automated sampling and analysis of seawater and has been used
to detect the presence of the algae responsible for causing red tide.
This report
provides a highlevel overview of the OPD and describes the software
that controls it, primarily as an aid to software developers who
may be called upon to maintain the software and expand its capabilities.
 Bounded
edge coloring is a generalization of the classical
edge coloring problem in which each edge has a specified minimum
color. We show that the problem is NPcomplete and
study several approximation algorithms for it.
Bounded edge coloring is an abstraction of an offline crossbar
scheduling problem and has implications for the minimum speedup
required to achieve ideal performance.
 Maximum
priority matching.
Let G=(V,E) be an undirected graph with n vertices and m edges,
in which each vertex u is assigned an integer priority in [1,n],
with 1 being the ``highest'' priority. Let M be a matching of G.
We define the priority score of M to be an nary integer in
which the ith mostsignificant digit is the number of vertices
with priority i that are incident to an edge in M.
This problem can be solved in O(mn) time using a variation
of the augmenting path method (Edmonds' algorithm).
A
separate paper gives an algorithm for the case of
bipartite graphs which is faster when the number of distinct
priorities is limited.
 Multicast switch scheduling. Packet scheduling in
crossbar switches
is an interesting and challenging problem. While the unicast case
is fairly wellunderstood, relatively little is known about
the multicast case. One version of this problem can
be formulated as an
edge group coloring
problem in bipartite graphs.
In this problem, each vertex in the input subset divides
its incident edges into groups. Edges belonging to
different groups at a given vertex are required to have different
colors. Edges in the same group may share a color.
The objective of the problem is to color all the edges using as
few colors as possible. Such a coloring corresponds to a crossbar
switch schedule that transfers multicast packets from inputs to
outputs in the fewest steps.
The problem is NPcomplete and the best approximation
algorithm known has a performance bound of
O(log n/log log n).
 Grafalgo
is a library of graph algorithms
and supporting data structures. It was developed primarily for
pedagogical purposes, and the code is designed to be reasonably
easy to read and understand.
This makes it relatively straightforward to modify and extend
the library for other purposes.
Github repository.
Doxygen
documentation
Attention Prospective Graduate Students: I am no longer accepting new students
Favorite Quotes

In theory, there's no difference between theory and practice.
In practice, there is. Jan L. A. van de Snepscheut

Don't worry about other people stealing your ideas.
If your ideas are any good, you'll have to ram them down peoples' throats.
Howard Aiken

A design is complete not when there is nothing more to add,
but when there is nothing more that can be taken away.
Antoine de SaintExupery

A scientific theory should be as simple as possible.
But no simpler.
Albert Einstein

I apologize for writing such a long letter. I did not have time
to write a shorter one. Blaise Pascal

Omit needless words. Theodore Strunk

Asking if computers can think is like asking if submarines can swim.
Edsger Dijkstra

The real question is not whether computers think, but whether people do.
B. F. Skinner

I think, therefore I am. Rene Descartes