Eulerian Paths with Regular Constraints
Eulerian Paths with Regular Constraints
复制标题
具有正则约束的欧拉路径
DOI：
10.4230/lipics.mfcs.2016.62
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Gal Vardi
中科院分区：
文献类型：
--
作者：
O. Kupferman;Gal Vardi
标号图，其中边由字母表Sigma中的字母标记，被广泛用于建模许多类型的
与操作、成本、所有者或其他相关的关系
属性。标号图中的每条路在Sigma^*中导出一个词
--通过将字母沿中的边缘连接而得到的字母
这条路。经典图论问题引发新问题
把这些词都考虑进去。我们介绍和研究了
约束欧拉路问题。问题的输入是一个
Sigma-标号图G和一个规范L\子集Sigma^*.
目标是在G中找到一条满足L.We的欧拉路
考虑由G的类定义的几类问题
和L.我们重点关注L的案件，并表明虽然
问题通常是NP完全的，即使对于非常简单的图和
规范，有一些类可以高效地解决。我们的
结果推广了关于具有边序约束的欧拉路的工作。我们
还研究了受约束的中国邮递员问题，其中
边是有成本的，目标是找到包含以下内容的最便宜路径
每条边至少一次，并且符合规格。最后，我们
定义和研究图的欧拉语言，即
欧拉路径上的一组单词。
Labeled graphs, in which edges are labeled by letters from some alphabet Sigma, are extensively used to model many types of
relations associated with actions, costs, owners, or other
properties. Each path in a labeled graph induces a word in Sigma^*
-- the one obtained by concatenating the letters along the edges in
the path. Classical graph-theory problems give rise to new problems
that take these words into account. We introduce and study the
constrained Eulerian path problem. The input to the problem is a
Sigma-labeled graph G and a specification L \subseteq Sigma^*.
The goal is to find an Eulerian path in G that satisfies L. We
consider several classes of the problem, defined by the classes of G
and L. We focus on the case L is regular and show that while the
problem is in general NP-complete, even for very simple graphs and
specifications, there are classes that can be solved efficiently. Our
results extend work on Eulerian paths with edge-order constraints. We
also study the constrained Chinese postman problem, where
edges have costs and the goal is to find a cheapest path that contains
each edge at least once and satisfies the specification. Finally, we
define and study the Eulerian language of a graph, namely the
set of words along its Eulerian paths.