Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory - (Extended Abstract)
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory - (Extended Abstract)
复制标题
有界排名宽度图的线性时间算法：使用博弈论的新面貌 - （扩展摘要）
DOI：
10.1007/978-3-642-20877-5_49
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Somnath Sikdar
中科院分区：
文献类型：
--
作者：
Alexander Langer;Peter Rossmanith;Somnath Sikdar
本文给出了Courcelle、Makowski和Rotics [6]的一个定理的另一种证明，该定理指出，对于有界秩宽的图，用MSO 1表示的问题在线性时间内是可解的。我们的证明使用博弈论的方法，并具有独立的优势。特别是，我们的演讲不假设任何逻辑或自动机理论的背景。此外，我们的方法可以推广到证明其他类似的结果，例如，Courcelle的树宽定理[3，19]。
We present an alternative proof of a theorem by Courcelle, Makowski and Rotics [6] which states that problems expressible in MSO1are solvable in linear time for graphs of bounded rankwidth. Our proof uses a game-theoretic approach and has the advantage of being self-contained. In particular, our presentation does not assume any background in logic or automata theory. Moreover our approach can be generalized to prove other results of a similar flavor, for example, that of Courcelle’s Theorem for treewidth [3,19].
登录
查看更多内容
有界秩宽图上更好的多项式算法
DOI：
10.1007/978-3-642-10217-2_27
发表时间：
2009
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
R. Ganian;Petr Hliněný
通讯作者：
Petr Hliněný
NP - P 中的稀疏集
DOI：
10.1016/0020-0190(83)90024-8
发表时间：
1982
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
J. Hartmanis
通讯作者：
J. Hartmanis
DOI：
10.2178/bsl.1804010
发表时间：
2012
期刊：
Bull. Symb. Log.
影响因子：
--
作者：
P. Maddy
通讯作者：
P. Maddy
DOI：
10.1007/978-3-540-74839-7_7
发表时间：
2007
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
B. Courcelle;M. Kanté
通讯作者：
M. Kanté
影响因子：
1
作者：
COURCELLE, B
通讯作者：
COURCELLE, B