A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems
A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems
复制标题
应用于多智能体系统的图形最大稳定集和着色问题的矩阵方法
DOI：
10.1016/j.automatica.2012.03.024
复制
发表时间：
2012-07
期刊：
影响因子：
6.4
通讯作者：
LIU Zhenbin
中科院分区：
文献类型：
--
作者：
WANG Yuzhen;Zhang chenghui;LIU Zhenbin
利用矩阵的半张量积，研究了图的最大（权）稳定集和顶点着色问题，并将其应用于多智能体系统的群体一致性问题，给出了一些新的结果和算法.首先，通过定义一个特征逻辑向量，利用逻辑函数的矩阵表示，得到了内稳定集问题的一个代数描述，并在此基础上建立了一个求任意图的所有内稳定集的新算法.其次，研究了最大（权）稳定集问题，给出了一个充分必要条件，并利用该条件得到了求所有最大（权）稳定集的算法。第三，利用半张量积方法研究了顶点着色问题，给出了顶点着色的两个充要条件，并在此基础上提出了一个求所有k-着色方案和最小着色划分的新算法。最后，将所得结果应用到多智能体系统中，并提出了一种新的协议设计过程的群体一致性问题。算例研究表明，本文的结果/算法是有效的。
Using the semi-tensor product of matrices, this paper investigates the maximum (weight) stable set and vertex coloring problems of graphs with application to the group consensus of multi-agent systems, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for the internally stable set problem, based on which a new algorithm to find all the internally stable sets is established for any graph. Secondly, the maximum (weight) stable set problem is considered, and a necessary and sufficient condition is presented, by which an algorithm to find all the maximum (weight) stable sets is obtained. Thirdly, the vertex coloring problem is studied by using the semi-tensor product method, and two necessary and sufficient conditions are proposed for the colorability, based on which a new algorithm to find all the k-coloring schemes and minimum coloring partitions is put forward. Finally, the obtained results are applied to multi-agent systems, and a new protocol design procedure is presented for the group consensus problem. The study of illustrative examples shows that the results/algorithms presented in this paper are very effective.
登录
查看更多内容
DOI：
--
发表时间：
1974
期刊：
--
影响因子：
--
作者：
S. Poljak
通讯作者：
S. Poljak
DOI：
10.1016/j.dam.2006.07.017
发表时间：
2003-05
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
P. Galinier;A. Hertz;N. Zufferey
通讯作者：
P. Galinier;A. Hertz;N. Zufferey
DOI：
10.1016/j.eswa.2011.01.098
发表时间：
2011-08
期刊：
Expert Syst. Appl.
影响因子：
--
作者：
J. A. Torkestani;M. Meybodi
通讯作者：
J. A. Torkestani;M. Meybodi
布尔控制网络的实现
影响因子：
6.4
作者：
Cheng, Daizhan;Li, Zhiqiang;Qi, Hongsheng
通讯作者：
Qi, Hongsheng
DOI：
10.1016/s0377-2217(02)00362-4
发表时间：
2003-08
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
J. Yáñez;J. Ramírez
通讯作者：
J. Yáñez;J. Ramírez