Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width
复制标题
DOI：
10.1007/10692760_1
复制
发表时间：
1998-06
期刊：
影响因子：
--
通讯作者：
B. Courcelle;J. Makowsky;Udi Rotics
中科院分区：
文献类型：
--
作者：
B. Courcelle;J. Makowsky;Udi Rotics
最多k个顶点宽度的图是由Courcelle，Engelfriet和Rozenberg（1993）提出的，它们可以用k个顶点标号的图运算的k-表达式来定义。本文证明了（q，q-4）图的团宽至多为q，P4-整齐图的团宽至多为4。Babel和Olariu（1995）提出的q，q-4）图扩展了P4-稀疏图，Hoàng（1985）提出的P4-稀疏图在调度、聚类和计算语义等领域有着广泛的应用. P4-稀疏图的另一个推广是Rusu（1995）引入的P4-整齐图，并证明了这类线性EMSOL（τ1，L）优化问题在O（f（|V|,|E|对于定义它的图Gan的表达式，可以在O（f（|V|,|E|））时间。最后，我们证明了上述结果不能推广到词汇表τ 2上的MSOL（τ2）决策和优化问题，因为词汇表τ 2允许边被认为是图的定义域的元素，从而除了在顶点上量化之外，还允许在边上量化。
Graphs of clique-width at mostkwere introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined byk-expressions based on graph operations which usekvertex labels. In this paper we show that the (q,q-4) graphs are of clique width at mostqandP4-tidy graphs are of clique-width at most4. Furthermore, thek-expression (fork=4 ork=q) associated with such a graph can be found in linear time.q,q-4) graphs were introduced by Babel and Olariu (1995) and extends the class ofP4-sparse graphs.P4-sparse graphs were introduced by Hoàng (1985) and are widely studied because of their applications in areas such as scheduling, clustering and computational semantics. Another extension ofP4-sparse graphs are theP4-tidy graphs which were introduced by Rusu (1995).Furthermore, we show that the class of LinEMSOL(τ1,L) optimization problems is solvable inO(f(|V|,|E|)) time on a class of graphs of clique-width at mostkin which for every graphGan expression defining it can be constructed inO(f(|V|,|E|)) time. By the above this applies in particular to (q,q– 4) graphs,P4-tidy graphs andP4-sparse graphs withflinear.Finally, we show that the above results cannot be extended to MSOL(τ2) decision and optimization problems on the vocabularyτ2which allow edges to be considered as elements of the domains of the graphs in question, and by that, allow quantifying over edges in addition to quantifying over vertices.