基于最大权重独立集的D2D资源分配研究，王明昕，彭涛，密集和复杂的场景下，一种更为灵活的频谱资源利用方式被认为可以满足日益增长的传输需求。D2D通信（设备与设备间通信）便是在这种

3-SAT归约到独立集问题 【3-SAT ≤p\leq_p≤p​ 独立集】 要证明3-SAT问题可以归约到独立集，就需要证明，有一个关于独立集的黑盒子，通过解3-SAT实例，能够解3-SAT问题。 图4为从3-SAT到独立集归约的一个实例。 图4 从3-SAT到独立集的归约 对于一个子句来说，只要有一项的值为真，则整个子句的值为真。 则，根据子句可以这样构造图：对于每一个子句，创建三个点，将三个点连接成三角形（如上图）。若存在两个子句中有x1x_1x1​和x‾1\overline x_1x1​,则在这两个节点之间添加一条边（称为冲突变，即这两边不能同时被选到）。 则，存在一个真值赋值，当且仅

在面向轨道的多假设跟踪器中重建全局假设的问题是 MWISP 的一个实例。 在 MHT 中，家族结构是已知的，可以用来为 MHT-MWISP 找到快速的本地搜索启发式。 类型 2 实例有许多小系列（其中 79 个），一个集群中有 231 条轨道。 提供它是为了促进与其他假设生成方法的比较。 类型 1 实例有 15 个系列，使用起来要容易得多。

最大独立集和最大集团在许多应用程序中都很有用。 列出它们的幼稚方式可能需要大量计算。 该包包含两个函数，BK_MaxIS 和 BK_MaxClique，它们使用 Bron-Kerbosch 算法分别列出给定无向图的所有最大独立集和最大团。 函数的输入是所需无向图的邻接矩阵 ( http://mathworld.wolfram.com/AdjacencyMatrix.html )。 返回值是一个 0-1 矩阵，其中每一列对应一个最大匹配，每一行对应一个顶点。 因此矩阵的大小为 m*n，其中 m 是图中顶点的数量，n 是最大独立集的数量。 位置 (i,j) 中的值 1 表示顶点 i 在由列 j 索引的最大独立集（或团）中处于活动状态。 例子： 要找到 3-path 的最大独立集： >> A = [0 1 0;1 0 1;0 1 0] >> BK_MaxIS(A) 答案 = 1 0

最大团问题的测试数据。 按照不同的数据规模整理，每一组测试数据都是精心构造的，对验证算法的有效性非常有帮助。 每一个文件就是一组输入，以邻接表的形式输入一个图。格式如下： 第一行： p edge 顶点数 边数 以下每一行： e 顶点号 顶点号 说明： p edge ， e 是固有的，顶点号从 1 开始。例如： p edge 4 3 e 1 2 e 2 3 e 3 4 文件的标题就是这个图的答案，即最大团的顶点数。

立集有着广泛的应用，尤其广泛应用于系统故障诊断领域。在求简单图极大独立集的程序实现方面，目前开展的研究工作还比较少。介绍简单图极大独立集的一种求取算法，剖析了该算法在使用面向对象程序设计模式中的实现方式，提出在定长字符串模式匹配中采用异或运算的运算法则来进行字符串模式匹配，由此作为多元式代数运算的基础对这个算法进行程序实现，并分析了这种字符串模式匹配的时闫效率。