Computational Combinatorics

Month: February, 2014

Best Practices for Backtrack Search Algorithms

Almost every algorithm I implement these days is a combinatorial search, which is a fancy way of saying a backtrack search to find combinatorial objects. A recursive algorithm determines a set of choices to make, selects one, and deepens the search. After all options are exhausted, the algorithm steps “up” a level of the search tree and makes a different choice.

Today, I want to discuss a few patterns I have developed in order to make such a backtracking search very error-proof and to make development streamlined. These concepts are particularly helpful when using TreeSearch.
Read the rest of this entry »

Best Practices for Scientific Computing

The following tweet found its way into my Twitter newsfeed.

I thought it would be appropriate to take the advice found in this article and apply them specifically to computational combinatorics. In particular, they identify and outline eight best practices, which I will discuss individually. Further, during the discussion I will include how I apply (or will apply) these concepts during my own development process. Below, I have simply copied their “Summary of Best Practices”. You can investigate each item in more detail in the original article. I’ll add my own ideas under each main topic.

Caveat: I showed this paper to a software engineer (my wife) and she thought all of these items would be obvious to anyone with even a basic understanding of software engineering. However, as the original paper is written for biologists and this blog is written for mathematicians, I find it appropriate to cover these ideas.
Read the rest of this entry »

Finding Cliques and Independent Sets in Circulant Graphs

We recently discussed cliquer, a “fast” algorithm for finding and counting maximum cliques in a graph. Today, I would like to discuss a modification of this algorithm when applied to graphs that have a very restrictive form of symmetry. Specifically, we will discuss circulant graphs and interval subgraphs of distance graphs. These graphs are particularly important for discovering the independence ratio of distance graphs, as discussed in the recently submitted paper, On the independence ratio of distance graphs with James Carraher, David Galvin, Stephen Hartke, and Jamie Radcliffe.

All code and data discussed is available at the distance graph page.
Read the rest of this entry »