首页 | 本学科首页   官方微博 | 高级检索  
     


Paths and trails in edge-colored graphs
Authors:A Abouelaoualim  KCh Das  L Faria  Y Manoussakis  C Martinhon  R Saad
Affiliation:1. University of Paris-XI, LRI, Bât. 490, 91405 Orsay Cedex, France;2. Estadual University of Rio de Janeiro, Department of Math., São Gonçalo, RJ, Brazil;3. Fluminense Federal University, Institute of Computation, Niterói, RJ, 24210-240, Brazil;4. 114/40 rue Charles Albanel, Gatineau (QC) J8Z 1R2, Canada
Abstract:This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices ss and tt in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−tst path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between ss and tt for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist kk pairwise vertex/edge disjoint properly edge-colored s−tst paths/trails in a cc-edge-colored graph GcGc is NP-complete even for k=2k=2 and c=Ω(n2)c=Ω(n2), where nn denotes the number of vertices in GcGc. Moreover, we prove that these problems remain NP-complete for cc-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)c=Ω(n). We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.
Keywords:Edge-colored graphs  Connectivity  Properly edge-colored paths  Trails and cycles
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号