最大独立集

摘要： 编码理论中的一个基本问题是求A(n,d,w)的值,即长度为n,重量为w,最小Hamming距离为d的二元码集的大小。它可看作是n维超立方体 次幂图中所有重量为w的点导出子图Qn(d-1,w)的最大独立集。本文运用构造图Qn(d-1,w)的最大独立集的方法得到n、d和w为某些特殊值时,A(n,d,w)=4 。

摘要： 编码理论中的一个基本问题是求A(n,d,w)的值,即最小Hamming距离为d的最大n长二元常重码集的大小。而A(n,d,w)又可看作是n维超立方体d-1次幂图中所有重量为w的点导出子图的最大独立集。故为探索的最大独立集,本文首次给出了图的定义,对其一些基本性质进行了研究并得到如下主要结果:是-正则图;是点传递图;对于2≤d≤3,若w≥[n/2],则;若w,则;当3≤d≤4时,有 或。

摘要： 编码理论中的一个基本问题是求最小Hamming距离为d的最大n长二元码集的大小,即求超立方体d-1次幂的最大独立集。本文运用构造超立方体d-1次幂最大独立集的方法得到几类特殊的A(n,d)的值:对于,如果,则A(n,d)=2;如果,则A(n,d)=4;如果n=3k,,且,则A(n,d)=4。

摘要： 最大独立集问题是著名的NP-hard问题,在许多领域都有广泛的实际应用.在给定无向图G=(V,E)中,最大独立集是顶点V的一个子集I,I中顶点的数量最大且任意2个顶点都不相邻.本文提出了一种启发式的最大独立集问题算法RI-DS-TS,本算法由3部分组成:随机初始化,基于度与支撑的顶点挑选,基于禁忌搜索的独立集优化.本文给出了RI-DS-TS算法的具体步骤,并使用DIMACS基准中的实例对RI-DS-TS算法进行了验证,通过和目前已知的最优结果对比,本算法在满足经济性的同时取得了令人满意的效果.

摘要： 设G=(V(G),E(G))为有限简单图,X是V(G)的子集.若X中任意两个点不相邻则称X是独立集.用core(G)表示G的所有最大独立集的交.X的差是指X的顶点数与其邻集的顶点数之差.在G的所有顶点子集中,差最大的子集即为G的临界集.用ker(G)表示G的所有临界集的交.在图G中,core(G)?ker(G);当图G为二部图时,则core(G)=ker(G).本文刻画了一类单圈图G的core(G)=ker(G)的结构.

摘要： 在无线传感器网络中,随机部署传感器节点导致节点的监测区域相互重叠,产生大量的监测冗余.针对部分覆盖目标场景即可满足监测需求的应用,如何激活尽可能少的节点以满足部分覆盖要求并保证网络连通性,是研究的难点.本文将目标场景划分为多个区域,在区域内依据最大独立集选择感知节点,然后跨区域建立树结构实现数据收集.首先采用网格模型计算节点监测面积和监测冗余,据此计算最大独立集,再按照节点的监测冗余与监测贡献面积来增删少量节点以达到监测要求,最终通过激活较少的感知节点实现部分覆盖.进而建立各区域感知节点到sink节点的数据收集树结构,对于不能加入树中的区域通过激活辅助传输节点来实现连通.除感知节点和辅助传输节点以外,其他节点进入休眠状态,从而节省能量,延长网络生命期.仿真结果表明,相较其他方法,本文提出的方法能够激活较少的节点来满足部分覆盖要求,降低能量消耗.

摘要： 针对H2 H/M2M共存的LTE-A全频复用异构蜂窝网络,提出基于最大独立集的干扰协调和RB扩展分配算法(CGMMIS算法),以在保证RB分配连续性的前提下优化系统和速率.首先,基于节点之间的相对干扰强度构建干扰图.然后,CGMMIS算法将存在强干扰的节点分到不同的独立集中,同时最大化独立集内各节点的信道增益之和.最后,利用RB扩展分配算法保证RB分配连续性,使得节点仅选择使其可达速率最大的独立集.仿真结果表明,在M2M设备密集部署的场景下,CGMMIS算法的系统和速率明显优于非协同算法和基于着色的最大独立集随机搜索算法.

摘要： 针对多信道无线网络下隐藏节点导致网络吞吐量下降的问题,提出了一种基于最大独立集(MIS)模型的多信道无线局域网介质访问控制(MAC)协议.该协议包括介质接入和信道分配2部分.其中,介质接入使用专用控制信道和发送请求/接收请求(RTS/CTS)握手机制;信道分配以MIS算法为基础,通过分布式算法实现.最后,利用OPNET仿真软件对该协议进行了分析和仿真.结果表明该协议可有效利用多信道资源,提升了无线网络性能,网络吞吐量比单信道协议提高了50％,同时降低了端到端延时.

摘要： 针对现有无线Mesh网络信道分配方案中的冲突模型不能反映真实网络干扰,提出一种基于信号干扰比(SIR)冲突图和最大独立集的信道分配方案.首先,由于射频信号的反射干扰远高于噪声,所以利用节点间的SIR代替传统信号干扰噪声比(SINR)来构建冲突图,同时考虑了节点累积干扰.然后,在冲突图基础上,通过提出的信道分配算法构建节点最大独立集,最终获得最低干扰的信道分配方案.实验结果表明,该方案在不同节点度下都具有较低的干扰比例和较高的网络吞吐量.

摘要： 提出了将地图着色问题转化为顶点着色问题,然后把顶点着色问题转化为求最大独立集问题.最大独立集问题的解法采用改进的粘贴DNA计算,即全信息化的DNA粘贴计算.DNA粘贴计算设计了主链和存储链,而且在生物计算中采用并行处理.最后给出了一个实例,详细说明了地图着色问题的解法,得出了最终的解.

摘要： 在分析排课系统特征的基础上,利用图论中最大独立集的理论,对排课资源进行合理抽象并建模,实现自动排课的功能要求,并进行算例分析.算例分析表明,该方法解决排课表问题相当实用,而且效率较高.该方法具有效性和可靠性.

摘要： 研究并得到了图的最大团和最大独立集的整数规划模型。本文利用布尔代数与整数规划基本理论相结合,建立了两个求解图的最大团的整数规划模型,改进了文献中的一个结论,并在此基础上得到了图的最大独立集的整数规划模型,最后利用算例对得到的结论进行了验证。

摘要： 本发明公开了一种基于DSP的最大功率独立供电系统，包括DCDC变换电路，由储能电感、功率开关管、二极管、电容和负载电阻构成；所述功率开关管具有耦接储能电感输出端的集电极、以及耦合连接电压负极端的发射极；所述电容串联连接二极管导通端，且并联连接负载电阻；所述DCDC变换电路的功率开关管导通后，电源的电压加到储能电感上，电感电流成线性増长，二极管截止，负载由电容提供；维持负载电阻继续工作，所述DCDC变换电路与蓄电池组之间设有防反充二极管；当太阳能电池发的电不能满足负载需要时，蓄电池组对负载进行放电，当蓄电池组放电时，所述防反充二极管正向导通，反向截止。

摘要： 本申请公开来自独立隔室的液位测量与最大冗余的组合。估计布置在可移动平台中或与可移动平台连接的第一流体隔室和第二流体隔室的流体相关量。将来自第一液位传感器、第二液位传感器、第三液位传感器、第四液位传感器的测量组合成统一计算。从统一计算来计算流体相关量，流体相关量包括以下所有：(1)流体定向估计，其对于第一流体隔室和第二流体隔室是共有的，(2)第一流体隔室的第一流体高度估计，和(3)第二流体隔室的第二流体高度估计，借此(1)、(2)、和(3)形成一组结果。

摘要： 本发明属于移动网络技术领域，公开了一种带权时变网络在耗费限制下的最大错误独立路径计算方法，所述带权时变网络在耗费限制下的最大错误独立路径计算方法包括：对通信网络基图建立线型图和对应的裂变图；对于裂变图，给出总花费限制下的度量指标MaxFlowδ的数学建模；根据整数规划表达式，用数学规划工具包求解最优的MaxFlowδ；利用求出的MaxFlowδ进行多路径路由，并在链路随机出错场景下，统计数据包发送的成功率。本发明同时考虑错误的时间特性和控制通信总成本耗费；采用网络流模型对问题进行建模，直观上使复杂数学问题形象化，还具有很好的可延伸性，通过线性对偶的方法扩展为在一定成本限制下求解最小割问题。

摘要： 本公开描述了用于减轻井下管柱中的振动的系统和方法。该方法包括：在钻井操作期间获得第一负荷和第二负荷的第一负荷测量结果和第二负荷测量结果；以及产生第一负荷测量数据和第二负荷测量数据，其中第一负荷传感器和第二负荷传感器被隔开传感器距离。从该第一负荷测量数据和该第二负荷测量数据以及该传感器距离确定该第一负荷和该第二负荷的第一代表性值和/或第二代表性值。将所确定的代表性值与相应负荷极限进行比较，并且响应于所确定的代表性值等于或超过该相应负荷极限而执行振动减轻操作。

摘要： 本发明提供一种存储器系统，其可包括：廉价磁盘冗余阵列组，即RAID组，其包括多个磁盘；以及存储访问层，其包括RAID引擎，其中RAID引擎适用于从RAID组请求数据、基于延迟阈值确定多个磁盘中的磁盘是否忙碌、当确定磁盘忙碌时确定被请求的数据是否可以从多个磁盘中的其它非忙碌磁盘获取以及当确定数据从其它非忙碌磁盘可获取时获取被请求的数据。

摘要： 本发明涉及独立级联模型下基于最大似然的影响力最大化方法。本发明在复杂网络中确定种子节点，构造基于抽样的缩略图以及顶点分层，计算构造的缩略图中所有顶点的最大似然概率值，对所有的最大似然概率值进行排序，筛选出k个节点。本发明克服了Degree方法在识别有影响力节点方面缺乏准确性，CascadeDiscount方法计算复杂，内存消耗大且运行时间也比较长等缺陷。本发明提出一种构造缩略图的方法从而将复杂网络进行分解，按照条件筛选出包含k个节点的种子节点集合S，避免之前算法中寻找最短路径等其他条件，从而减少了许多不必要的计算，使得预测结果更加的准确，可靠性更高。

摘要： 本发明提供了一种基于独立级联模型面向社交网络群体影响力最大化的方法，所述方法包括以下步骤：步骤S1、构建基于双层模型的社交网络模型；步骤S2、在社交网络模型中，建立基于独立级联模型的社交网络群体影响最大化问题模型；步骤S3、在社交网络群体影响最大化问题模型中，生成节点的反向可达集；步骤S4、从反向可达集生成节点的反向可达集中，选择k个覆盖最多反向可达集的节点作为种子节点；本发明能够实现在有限的计算资源下，最大程度地提高解决社交网络群体影响最大化问题效率。

摘要： 本发明属于移动网络技术领域，公开了一种带权时变网络在耗费限制下的最大错误独立路径计算方法，所述带权时变网络在耗费限制下的最大错误独立路径计算方法包括：对通信网络基图建立线型图和对应的裂变图；对于裂变图，给出总花费限制下的度量指标MaxFlowδ的数学建模；根据整数规划表达式，用数学规划工具包求解最优的MaxFlowδ；利用求出的MaxFlowδ进行多路径路由，并在链路随机出错场景下，统计数据包发送的成功率。本发明同时考虑错误的时间特性和控制通信总成本耗费；采用网络流模型对问题进行建模，直观上使复杂数学问题形象化，还具有很好的可延伸性，通过线性对偶的方法扩展为在一定成本限制下求解最小割问题。

摘要： 本发明公开了一种基于最大独立集的MIMO IC链式干扰对齐方法，旨在解决现有技术中信道状态信息矩阵选取固定，收发节点的天线利用率低的条件限制。实现步骤为：设置系统参数；构建MIMO干扰信道的部分连接模型；生成每个接收端的发送端集合；生成每个接收端的干扰对齐方案；构建代表干扰对齐方案的冲突图；生成冲突图的最大独立集；构建干扰对齐链方程；生成解码矩阵；每个发送端同时发送数据流；消除接收端的干扰信号；在每个接收端处得到无干扰的期望信号，结束干扰对齐。本发明增加了对齐的干扰范围，提升了天线利用率，增加了系统自由度和信道传输速率。

摘要： 本发明公开了一种单位圆盘图上的最大独立集近似求解方法，包括以下步骤：步骤1：利用动态规划方法设计一种单位圆盘顶点的相邻顶点集诱导子图的最大顶点独立集的最优解求解方法，并给出任意两顶点相邻顶点集并集诱导子图的最大顶点独立集的最优解；步骤2：针对一般的单位圆盘图，首先计算顶点支配独立集；之后对顶点支配独立集中成员进行单独检查，判断结果是否可优化，得到中间解；最后对中间解中成员进行联合检查，判断结果是否可优化，得到最终解。本发明以O(Δ