Home
Teaching
Papers
Presentations
Software
Other

SearchLib is a collection of projects with a common goal: search for combinatorial structures.
Each project is customized to the problem at hand, but there are common elements.
The first is the use of TreeSearch for the structure of the search, giving a common interface for all input/output management and statistics tracking.
The second is the consideration of symmetries of the objects.
To compute automorphisms and canonical labelings, we use Brendan McKay's nauty software.
The most recent stable version of SearchLib can be downloaded on a projectbyproject basis.
The nauty library must be downloaded separately to comply with licenses.

TreeSearch 
An abstract implementation of a backtracking search to allow automatic parallel job generation. Includes scripts for input/output management on a grid using the Condor scheduler. Forms the base of all other projects in SearchLib.

Source

User Guide


Utilities 
This package contains classes, methods, and executables that are used by other projects.

Source

User Guide


EarSearch 
Generates 2connected graphs by ear decompositions using an isomorphfree generation scheme.
Requires: nauty.

Source

User Guide


ChainCounting 
Generates widthtwo posets and counts the number of chains in each,
searching for representations of all positive integers. Found representations for all integers up to 7.38 million.
Joint work with Elizabeth Kupin and Benjamin M. Reiniger.

Source

User Guide


Saturation 
Generates uniquely K_{r}saturated graphs using a custom augmentation.
Uses orbital branching or isomorphfree generation.
Found several new graphs of orders 13, 15, 16, and 18 and a new infinite family.
Requires: nauty and cliquer.
Joint work with Stephen G. Hartke.

Source

User Guide


Progressions 
Searches for extremal colorings of [n] which avoid different types of progressions which generalize arithmetic progressions. Also restricts to symmetric colorings of [n].
Joint work with Adam S. Jobson and André E. Kézdy.

Source

User Guide


MMSConjecture 
Searches for vectors of $n$ real numbers with nonnegative sum while minimizing the number of nonnegative partial $k$sums.
Verifies the ManickamMiklósSinghi Conjecture for $k \leq 7$.
Joint work with Stephen G. Hartke.

Source

User Guide

This software was created with support from the National Science Foundation, grants CCF0916525 and DMS0914815.
