Computational Combinatorics

Category: Uncategorized

Happy Birthday, Joan Hutchinson!

Bernard Lidický and I organized an AMS Special Session on Extremal and Structural Graph Theory last weekend. It was a wonderful session, filled with wonderful speakers talking about some amazing mathematics.

Notably missing was Joan Hutchinson, who we invited but she declined because she was celebrating a milestone birthday on Sunday. That’s a very good reason to miss the session, and we missed her greatly. However, we did want to share our well-wishes.

Thanks to all who helped with the session and the making of this video! A few participants were missing at the time of filming, but you can try finding your favorite graph theorists in the (very short) video above.

Announcement: Computational Combinatorics at CanaDAM

A quick announcement to those who may be interested. Jan Goedgebeur, who has done many nice things including the wonderful House of Graphs, is organizing a Minisymposium at CanaDAM this summer. The minisymposium is Algorithmic Construction of Combinatorial Objects and will be on June 2, after Brendan McKay’s plenary talk (regular readers will remember him from several topics). See the CanaDAM 2015 page for more details about the larger conference. Unfortunately, I cannot attend, as I will be busy at that time.

GRWC 2015 Announcement

We take a small break from our usual discussions in order to announce that applications for GRWC 2015 are now online! See the announcement below.

Read the rest of this entry »

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 »

Things a Graph Theorist Should Do at Least Once

The theory blogs have been repeating the idea of “Things a [insert field] researcher should do at least once” including theoretical computer science, complexity theory, and algorithmic game theory. I figured I should chime in with what a graph theorist should do at least once.
Read the rest of this entry »