Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs

机译：弧形有向图的路径，轨迹和电路的复杂性

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We deal with different algorithmic questions regarding properly arc-colored s-t paths, trails and circuits in arc-colored digraphs. Given an arc-colored digraph D~c with c > 2 colors, we show that the problem of maximizing the number of arc disjoint properly arc-colored s-t trails can be solved in polynomial time. Surprisingly, we prove that the determination of one properly arc-colored s-t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c = Ω(n), where n denotes the number of vertices in D~c. If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex x (resp., properly arc-colored Hamiltonian s-t path) is NP-complete, even if c = 2. As a consequence, we solve a weak version of an open problem posed in Gutin et. al. [17].

机译：我们处理关于圆弧色有向图中正确的圆弧色s-t路径，轨迹和电路的不同算法问题。给定一个c> 2种颜色的弧形有色图D〜c，我们证明了在多项式时间内可以解决最大化弧形不相交的数目的问题，而弧形s-t轨迹正确。出乎意料的是，我们证明即使对于不包含适当弧形电路且c =Ω（n）的平面图，确定一个适当弧形s-t路径也是NP完全的，其中n表示D〜c中的顶点数。如果有向图是弧形的锦标赛，则表明即使确定c =，它是否包含通过给定顶点x的正确弧形电路（即，正确的弧形哈密顿量st路径），也是NP完全的。因此，我们解决了Gutin等人提出的开放问题的一个弱版本。等[17]。

著录项

来源
《Theory and application of models of computation》|2010年|p.222-233|共12页
会议地点 Prague(CZ);Prague(CZ);Prague(CZ)
作者
Laurent Gourves; Adria Lyra; Carlos Martinhon; Jerome Monnot;
展开▼
作者单位

CNRS, FRE 3234, F-75775 Paris, France,Universite de Paris-Dauphine, LAMSADE, F-75775 Paris, France;

Fluminense Federal University, Inst. of Comp., Niteroi, RJ, 24210-240, Brazil ,Fed. Center of Techn. Educ. Celso S. Fonseca, CEFET/RJ, 26041-271, Brazil;

Fluminense Federal University, Inst. of Comp., Niteroi, RJ, 24210-240, Brazil;

CNRS, FRE 3234, F-75775 Paris, France,Universite de Paris-Dauphine, LAMSADE, F-75775 Paris, France;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词
arc-colored digraphs; properly arc-colored paths/trails and circuits; hamiltonian directed path; arc-colored tournaments; polyno-mial algorithms; NP-completeness;

机译：弧形有向图；弧形的路径/线路和电路是否正确；哈密尔顿定向路径；弧形比赛；多项式算法； NP完全性;

相似文献

外文文献
中文文献
专利

1. Complexity of trails, paths and circuits in arc-colored digraphs (Conferenc Paper) [J] . Gourvès L., Lyra A., Martinhon C.A., Discrete Applied Mathematics . 2013,第6期

机译：弧形有向图的轨迹，路径和电路的复杂性（会议论文）
2. Kernels by properly colored paths in arc-colored digraphs [J] . Bai Yandong, Fujita Shinya, Zhang Shenggui Discrete mathematics . 2018,第6期

机译：通过弧形上色的正确彩色路径粒
3. A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs [J] . Byoung-SongChwe International journal of mathematics and mathematical sciences . 1994,第3期

机译：有向图上欧拉路径和回路的一些Schützenberger型结果的证明
4. Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs [C] . Laurent Gourves, Adria Lyra, Carlos Martinhon, International Conference on Theory and Applications of Models of Computation . 2010

机译：弧形数字的路径，小径和电路的复杂性
5. Automatic mapping of off-road vehicle trails and paths at Fort Riley Installation, Kansas. [D] . Oller, Adam. 2012

机译：堪萨斯州赖利堡安装公司的越野车步道和路径的自动映射。
6. Following TRAILs path in the immune system [O] . Christina Falschlehner, Uta Schaefer, Henning Walczak 2009

机译：遵循TRAIL的免疫系统之路
7. Complexity of trails, paths and circuits in arc-colored digraphs [O] . Gourvès, Laurent, Lyra, Adria, Martinhon, Carlos A., 2013

机译：弧形有向图的轨迹，路径和电路的复杂性
8. The Expected Time Complexity of Parallel Graph and Digraph Algorithms. [R] . Reif, J. H., Spirakis, P. 1982

机译：并行图和有向图算法的期望时间复杂度。

Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs

摘要

著录项

相似文献

相关主题

期刊订阅