FPT Algorithms Exploiting Carving Decomposition for Eulerian Orientations and Ice-Type Models
FPT Algorithms Exploiting Carving Decomposition for Eulerian Orientations and Ice-Type Models
复制标题
利用雕刻分解实现欧拉方向和冰型模型的 FPT 算法
DOI：
10.1007/978-3-319-75172-6_19
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. Imai
中科院分区：
文献类型：
--
作者：
S. Shiroshita;T. Ogasawara;H. Hiraishi;H. Imai
无向图的欧拉定向是一种边的定向，使得对于每个顶点，入度和出度都相同。欧拉取向在许多领域都很重要。在统计物理学中，所谓冰模型的配分函数，是冰型模型的特例，与4正则图的欧拉方向数有关，这是它的Tutte多项式在该点的值。4-正则图中欧拉方向数的计算问题是P-完全的，但对于图的树宽却有一个固定参数可处理的FPT（Fixed Parameter Tractable）算法，本文提出了两个基于雕刻分解的FPT算法。其中一个计算一般图的欧拉方向数，另一个计算4-正则图的一般冰型模型的划分函数，其中k为输入图的切割宽度，k为顶点集的大小。
An Eulerian orientation of an undirected graph is an orientation of edges such that, for each vertex, both the indegree and the outdegree are the same. Eulerian orientations are important in a variety of fields. In statistical physics, the partition function of the so-called ice model, which is the special case of the ice-type model, is related to the number of Eulerian orientations of a 4-regular graph, which is the value of its Tutte polynomial at the point. The problem of counting the number of Eulerian orientations in a 4-regular graph is #P-complete, and yet there is an FPT (Fixed Parameter Tractable) algorithm for it with respect to the tree-width of the graph.This paper presents two FPT algorithms based on a carving decomposition. One of them counts the number of Eulerian orientations for a general graph intime andmemory consumption, and the other calculates the partition function of a general ice-type model for a 4-regular graph intime andmemory consumption where, for an input graph,kis the carving-width andnis the size of the vertex set.
登录
查看更多内容
评估有界树宽度图的 Tutte 多项式
DOI：
--
发表时间：
1998
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
S. Noble
通讯作者：
S. Noble
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
P. Creed
通讯作者：
P. Creed
比较 17 个图形参数
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Róbert Sasák
通讯作者：
Róbert Sasák
有界树宽图的 Tutte 多项式的算法
影响因子：
0.8
作者：
A. Andrzejak
通讯作者：
A. Andrzejak
4-正则图中计算欧拉游览的复杂性
影响因子：
1.1
作者：
Qi Ge;Daniel Stefankovic
通讯作者：
Daniel Stefankovic