Single Cluster Graph Partitioning for Robotics Applications

Proceedings of Robotics Science and Systems, 2005

PDF thumbnail
(PDF, 513.3 KB )


We present SCGP, an algorithm for finding a single cluster of well-connected nodes in a graph. The general problem is NP-hard, but our algorithm produces an approximate solution in O(N^2) time by considering the spectral properties of the graph�s adjacency matrix. We show how this algorithm can be used to find sets of self-consistent hypotheses while rejecting incorrect hypotheses, a problem that frequently arises in robotics. We present results from a range-only SLAM system, a polynomial time data association algorithm, and a method for parametric line fitting that can outperform RANSAC.


    AUTHOR     = {Edwin Olson and Matthew Walter and John Leonard and Seth Teller},
    TITLE      = {Single Cluster Graph Partitioning for Robotics Applications},
    BOOKTITLE  = {Proceedings of Robotics Science and Systems},
    PAGES      = {265-272},
    YEAR       = {2005},