Graph Matching: Relax at Your Own Risk.

Graph matching-aligning a pair of graphs to minimize their edge disagreements-has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics. Its attention can be partially attributed to its computational difficulty. Although many heuristics have previously been proposed in the literature to approximately solve graph matching, very few have any theoretical support for their performance.

Fast approximate quadratic programming for graph matching.

Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm.

The generalized spherical homeomorphism theorem for digital images.

The spherical homeomorphism conjecture, proposed by Shattuck and Leahy in 2001, serves as the backbone of their algorithm to correct the topology of magnetic resonance images of the human cerebral cortex. Using a canonical image-thickening technique and the authors' previously proven "spherical homeomorphism theorem for surfaces," we formulate and prove a spherical homeomorphism theorem which is valid for all digital images when utilizing the (26,6)-connectivity rule.

A proof of the spherical homeomorphism conjecture for surfaces.

The human cerebral cortex is topologically equivalent to a sphere when it is viewed as closed at the brain stem. Due to noise and/or resolution issues, magnetic resonance imaging may see "handles" that need to be eliminated to reflect the true spherical topology. Shattuck and Leahy present an algorithm to correct such an image.