23 citations · 42 across the 17 of their papers we have counts for
4 papers · 1 filter
A Partition-Based Relaxation For Steiner Trees
Jochen Konemann, David Pritchard, Kunlun Tan
The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G…
Efficient Divide-and-Conquer Implementations Of Symmetric FSAs
David Pritchard
A deterministic finite-state automaton (FSA) is an abstract sequential machine that reads the symbols comprising an input word one at a time. An FSA is symmetric if its output is i…
Nearest Neighbor Network Traversal
David Pritchard
A mobile agent in a network wants to visit every node of an n-node network, using a small number of steps. We investigate the performance of the following ``nearest neighbor'' heur…
Fast Computation of Small Cuts via Cycle Space Sampling
David Pritchard, Ramakrishna Thurimella
We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at eac…