BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jonathan Turner appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We provide a search method for Legendre pairs of composite length based on generating binary matrices with fixed row and column sums from compressed, complementary integer vectors. This approach yielded the first construction of a Legendre pair of length $77$, as well as the first exhaustive generation of Legendre pairs of length $55$.
This report provides an (updated) overview of {\sl Grafalgo}, an open-source library of graph algorithms and the data structures used to implement them. The programs in this library were originally written to support a graduate class in advanced data structures and algorithms at Washington University. Because the code's primary purpose was pedagogical, it was written to be as straightforward as possible, while still being highly efficient. Grafalgo is implemented in C++ and incorporates some features of C++11. The library is available on an open-source basis and may be downloaded from https://code.google.com/p/grafalgo/. Source code documentation is at www.arl.wustl.edu/\textasciitilde jst/doc/grafalgo. While not designed as production code, the library is suitable for use in larger systems, so long as its limitations are understood. The readability of the code also makes it relatively straightforward to extend it for other purposes.
A maximum priority matching is a matching in an undirected graph that maximizes a priority score defined with respect to given vertex priorities. An earlier paper showed how to find maximum priority matchings in unweighted graphs. This paper describes an algorithm for bipartite graphs that is faster when the number of distinct priority classes is limited. For graphs with $k$ distinct priority classes it runs in $O(kmn^{1/2})$ time, where $n$ is the number of vertices in the graph and $m$ is the number of edges.
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 $n$-ary integer in which the $i$-th most-significant digit is the number of vertices with priority $i$ that are incident to an edge in $M$. We describe a variation of the augmenting path method (Edmonds' algorithm) that finds a matching with maximum priority score in $O(mn)$ time.
This paper introduces a variant of the classical edge coloring problem in graphs that can be applied to an offline scheduling problem for crossbar switches. We show that the problem is NP-complete, develop three lower bounds bounds on the optimal solution value and evaluate the performance of several approximation algorithms, both analytically and experimentally. We show how to approximate an optimal solution with a worst-case performance ratio of $3/2$ and our experimental results demonstrate that the best algorithms produce results that very closely track a lower bound.
This paper introduces a natural generalization of the classical edge coloring problem in graphs that provides a useful abstraction for two well-known problems in multicast switching. We show that the problem is NP-hard and evaluate the performance of several approximation algorithms, both analytically and experimentally. We find that for random $χ$-colorable graphs, the number of colors used by the best algorithms falls within a small constant factor of $χ$, where the constant factor is mainly a function of the ratio of the number of outputs to inputs. When this ratio is less than 10, the best algorithms produces solutions that use fewer than $2χ$ colors. In addition, one of the algorithms studied finds high quality approximate solutions for any graph with high probability, where the probability of a low quality solution is a function only of the random choices made by the algorithm.