Distracted by research

I'll be posting very lightly for about week while I actually do some research.

I've been at war with the Graph Isomorphism problem for about nine years (very Trojan). This war has been characterized by fierce battles with long lulls of recuperation and frustration in between. Sometimes, I simply get stuck and have to work on something else.

I've been stuck for the past few months. I thought I'd finally addressed one of the few remaining issues back in March when I got an unexpected result that could be due either to an algorithm defect or a programming bug.

Debugging this one is hellish. I finally figured it out a few days ago.

The verdict: An algorithm defect. Actually, one I'd thought of before but hadn't properly dealt with.

My graph isomorphism algorithm constructs a canonical form for each graph and then compares the two canonical forms. If they are identical except for labeling, the graphs are isomorphic; otherwise, they are not. This part has been working fine since February.

People often don't just want to know that the two graphs are isomorphic, however - they want it proven to them by the exhibition of a mapping from the node labels of one graph to the node labels of the other. Take such a mapping and apply it to the first graph, and the two graphs should be identical up to and including labeling.

My algorithm for constructing this mapping is missing something. I'm working on fixing it. Once done, if I'm right, I'll have one more thing to prove, but the overall algorithm should work correctly for all graphs.

All of which means that I've got to spend most of my spare time for a bit on graph isomorphism rather than writing up other research.

I'll try to post daily with lagniappe and random thoughts.

Lagniappe

The Inner Life of the Cell, created by a group at Harvard, is an astounding computer-generated animation of what occurs within a cell. Several versions are available.

The version I would watch first has music.

Three more versions are found on this page, each having narration that explains what you are seeing.

Free Rice is an interesting vocabulary building site that contributes 20 grains of rice to UN World Food Program for each word that you get right.

The Big Spanish Castle has a cool optical illusion.

Copyright and Legal Notices

All Rights Reserved.