A popular paradigm for 3D point cloud registration is by extracting 3D
keypoint correspondences, then estimating the registration function from the
correspondences using a robust algorithm. However, many existing 3D keypoint
techniques tend to produce large proportions of erroneous correspondences or
outliers, which significantly increases the cost of robust estimation. An
alternative approach is to directly search for the subset of correspondences
that are pairwise consistent, without optimising the registration function.
This gives rise to the combinatorial problem of matching with pairwise
constraints. In this paper, we propose a very efficient maximum clique
algorithm to solve matching with pairwise constraints. Our technique combines
tree searching with efficient bounding and pruning based on graph colouring. We
demonstrate that, despite the theoretical intractability, many real problem
instances can be solved exactly and quickly (seconds to minutes) with our
algorithm, which makes our approach an excellent alternative to standard robust
techniques for 3D registration.

本文提出了一种非常高效的最大团算法，通过组合策略和基于图着色的边界和修剪，解决了匹配的成对约束问题，从而解决了三维点云配准中的问题。

基于配对约束的可实践最大团算法

A Practical Maximum Clique Algorithm for Matching with Pairwise  Constraints

We propose a fast, parallel maximum clique algorithm for large sparse graphs
that is designed to exploit characteristics of social and information networks.
The method exhibits a roughly linear runtime scaling over real-world networks
ranging from 1000 to 100 million nodes. In a test on a social network with 1.8
billion edges, the algorithm finds the largest clique in about 20 minutes. Our
method employs a branch and bound strategy with novel and aggressive pruning
techniques. For instance, we use the core number of a vertex in combination
with a good heuristic clique finder to efficiently remove the vast majority of
the search space. In addition, we parallelize the exploration of the search
tree. During the search, processes immediately communicate changes to upper and
lower bounds on the size of maximum clique, which occasionally results in a
super-linear speedup because vertices with large search spaces can be pruned by
other processes. We apply the algorithm to two problems: to compute temporal
strong components and to compress graphs.

该论文提出了一种快速、并行的最大团算法，特别适用于求解大型稀疏图，具备线性运行时特性，并且采用巧妙的预剪枝和分支策略，通过核心数和启发式算法发现关键点，同时使用并行搜索树加速探索；应用该算法计算强时间连通性和压缩图。