Abstract. In this work we provide a decomposition theorem for a class of quaternary signed-graphic matroids. The decomposition is based on [Formula: see text]-sums and a new operation called star composition, while the building blocks are graphic matroids and nongraphic matroids which become graphic upon the deletion of any cocircuit. This result generalizes previous results for binary signed-graphic matroids and graphic matroids, and it provides the theoretical basis for a recognition algorithm.

In this paper we employ Tutte's theory of bridges to derive a decomposition theorem for binary matroids arising from signed graphs. The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not based on $k$-sums but rather on the operation of deletion of a cocircuit. Specifically, it is shown that certain minors resulting from the deletion of a cocircuit of a binary matroid will be graphic matroids, apart from exactly one that will be signed-graphic, if and only if the matroid is signed-graphic.

We describe Fortran subroutines for finding approximate solutions of sparse instances of the Quadratic Assignment Problem (QAP) using a Greedy Randomized Adaptive Search Procedure (GRASP). The design and implementation of the code are described in detail. Computational results comparing the new subroutines with a dense version of the code (Algorithm 754, ACM TOMS) show that the speedup increases with the sparsity of the data.