Computational Combinatorics Roundup: December-January

by Derrick Stolee

I’m a little late in compiling the late December to January roundup, but here we go. As always, send me an email if you have a blog post, paper, or other resource that I can put in the next roundup.

Online Resources

Nauty and Traces by McKay and Piperno. Not only is there a new version of nauty, but there is a new algorithm, traces, which seems to run even faster. McKay and Piperno released a preprint of their new algorithm, given below (and you can see Piperno’s Search Space Contraction in Canonical Labeling of Graphs for an earlier discussion of traces). Not only is this an exciting development, but their website is an impressive way to disseminate their software. All software projects should have pages this impressive.

Sébastien Labbé wrote about Percolation and self-avoiding walks using Sage.

Research Papers

Tamara G. Kolda, Ali Pinar, Todd Plantenga, C. Seshadhri, Christine Task, Counting Triangles in Massive Graphs with MapReduce, arXiv:1301.5887 [cs.SI].
The authors investigate the very real implementation of counting triangles in a very large, dense graphs using the distributed computing process MapReduce. The clustering coefficient is roughly the probability that selecting a vertex and two of its neighbors will form a triangle. Calculating these numbers is important for understanding the structure of large networks.

Ioannis Katsikarelis, Computing bounded-width tree and branch decompositions of k-outerplanar graphs, arXiv:1301.5896 [cs.DS]
A graph is k-outerplanar essentially if there are k “layers” to the planar embedding: removing the vertices on the outer face reveals a (k-1)-outerplanar embedding. Katsikarelis reproves a bound of at most 3k-1 on the treewidth of a k-outerplanar graph and uses this bound to show efficiency of some algorithms on these graphs.

Brendan D. McKay, Adolfo Piperno, Practical Graph Isomorphism II, arXiv:1301.1493 [cs.DM].
As discussed above, Mckay and Piperno revised the original nauty algorithm for a measurable speedup. A substantial performance comparison to other solvers is presented. The new traces algorithm is particularly well-suited for known graphs with high local symmetry, such as strongly regular graphs.