« Where do I draw the line? | Home | Tsukurimashou 0.7 »

Cycle counting: the next generation

Wed 30 Jan 2013 by mskala Tags used:

Here are the slides (PDF) and an audio recording (MP3, 25 megabytes, 54 minutes) from a talk I gave today about one of my research projects. You'll get more out of it if you have some computer science background, but I hope it'll also be accessible and interesting to those of my readers who don't. I managed to work in Curious George, Sesame Street, electronics, XKCD, the meaning of "truth," and a piece of software called ECCHI. I plan to distribute the "Enhanced Cycle Counter and Hamiltonian Integrator" publicly at some point in the future. Maybe not until after the rewrite, though.

Abstract for the talk:

It is a #P-complete problem to find the number of subgraphs of a given labelled graph that are cycles. Practical work on this problem splits into two streams: there are applications for counting cycles in large numbers of small graphs (for instance, all 12.3 million graphs with up to ten vertices) and software to serve that need; and there are applications for counting the cycles in just a few large graphs (for instance, hypercubes). Existing automated techniques work very well on small graphs. In this talk I review my own and others' work on large graphs, where the existing results have until now required a large amount of human participation, and I discuss an automated system for solving the problem in large graphs.

0 comments



(optional field)
(optional field)
Answer "bonobo" here to fight spam. ここに「bonobo」を答えてください。SPAMを退治しましょう!
I reserve the right to delete or edit comments in any way and for any reason.