On the Performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs

The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.

From Working Memory to Long-term Memory and Back: Linked but Distinct

Neural models have proposed how short-term memory (STM) storage in working memory and long-term memory (LTM) storage and recall are linked and interact, but are realized by different mechanisms that obey different laws. The authors' data can be understood in the light of these models, which suggest that the authors may have gone too far in obscuring the differences between these processes.

Multi-Area Visuotopic Map Complexes in Macaque Striate and Extra-striate Cortex

We propose that a simple, closed-form mathematical expression--the Wedge-Dipole mapping--provides a concise approximation to the full-field, two-dimensional topographic structure of macaque V1, V2, and V3. A single map function, which we term a map complex, acts as a simultaneous descriptor of all three areas. Quantitative estimation of the Wedge-Dipole parameters is provided via 2DG data of central-field V1 topography and a publicly available data set of full-field macaque V1 and V2 topography. Good quantitative agreement is obtained between the data and the model presented here. The increasing importance of fMRI-based brain imaging motivates the development of more sophisticated two-dimensional models of cortical visuotopy, in contrast to the one-dimensional approximations that have been in common use. One reason is that topography has traditionally supplied an important aspect of "ground truth", or validation, for brain imaging, suggesting that further development of high-resolution fMRI will be facilitated by this data analysis. In addition, several important insights into the nature of cortical topography follows from this work. The presence of anisotropy in cortical magnification factor is shown to follow mathematically from the shared boundary conditions at the V1-V2 and V2-V3 borders, and therefore may not causally follow from the existence of columnar systems in these areas, as is widely assumed. An application of the Wedge-Dipole model to localizing aspects of visual processing to specific cortical areas--extending previous work in correlating V1 cortical magnification factor to retinal anatomy or visual psychophysics data--is briefly discussed.