Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
复制标题
表征秩宽度和平衡图表达式的图运算
DOI：
10.1007/978-3-540-74839-7_7
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Kanté
中科院分区：
文献类型：
--
作者：
B. Courcelle;M. Kanté
图的复杂性度量，如树宽、树宽、NLC宽和秩宽是重要的，因为它们产生固定参数可处理算法。秩宽度是基于GF（2）上图的邻接矩阵的秩。在这里，我们提出了代数运算的图的特征秩宽度。为了算法的目的，用平衡项来表示图是很重要的。我们给出了一个唯一的定理，推广了几个“平衡定理”的树宽度和campus宽度。对秩宽度和群宽度的一个变体m-群宽度得到了新的结果。
Graph complexity measures like tree-width, clique-width, NLC-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. Rank-width is based on ranks of adjacency matrices of graphs over GF(2). We propose here algebraic operations on graphs that characterize rank-width. For algorithmic purposes, it is important to represent graphs by balanced terms. We give a unique theorem that generalizes several "balancing theorems" for tree-width and clique-width. New results are obtained for rank-width and a variant of clique-width, called m-clique-width.