Search

Abstract: In this paper we deal from an algorithmic perspective with different questions regarding monochromatic and properly edge-colored s-t paths/trails on edge-colored graphs. Given a c-edge-colored graph without properly edge-colored closed trails, we present a polynomial time procedure for the determination of properly edge-colored s-t trails visiting all vertices of a prescribed number of times. As an immediate consequence, we polynomially solve the Hamiltonian path (resp., Eulerian trail) problem for this particular class of graphs. In addition, we prove that to check whether contains 2 properly edge-colored s-t paths/trails with length at most is NP-complete in the strong sense. Finally, we prove that, if is a general c-edge-colored graph, to find 2 monochromatic vertex disjoint s-t paths with different colors is NP-complete. [Copyright &y& Elsevier]

We introduce a number of problems regarding edge-color modifications in edge-colored graphs and digraphs. Consider a property π , a c -edge-colored graph G c not satisfying π , and an edge-recoloring cost matrix R = [ r i j ] c × c where r i j ≥ 0 denotes the cost of changing color i of edge e to color j . Basically, in this kind of problem the idea is to change the colors of one or more edges of G c in order to construct a new edge-colored graph such that the total edge-recoloring cost is minimized and property π is satisfied. We also consider the destruction of potentially undesirable structures with the minimum edge-recoloring cost. In this paper, we are especially concerned with the construction and destruction of properly edge-colored and monochromatic paths, trails and cycles in graphs and digraphs. Some related problems and future directions are presented. [ABSTRACT FROM AUTHOR]

Abstract: We deal with different algorithmic questions regarding properly arc-colored trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph with colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored path is NP-complete even for planar digraphs containing no properly arc-colored circuits and , where denotes the number of vertices in . 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 (resp., properly arc-colored Hamiltonian path) is NP-complete for . As a consequence, we solve a weak version of an open problem posed in Gutin et al. (1998) [23], whose objective is to determine whether a -arc-colored tournament contains a properly arc-colored circuit. [Copyright &y& Elsevier]

In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph Gc, we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in Gc, we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in Gc with endpoints in S. Further, if Gc contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs Gc containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in Abouelaoualim et. al.(2008), the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if Gc is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems. [ABSTRACT FROM AUTHOR]

Abstract: This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices and . This route can be a walk, a trail or a path. Each time a vertex is crossed by a walk there is an associated non-negative reload cost , where and denote, respectively, the colors of successive edges in this walk. The goal is to find a route whose total reload cost is minimum. Polynomial algorithms and proofs of NP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when reload costs are symmetric (i.e., ) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs. [Copyright &y& Elsevier]

Abstract: This paper presents two new randomized distributed algorithms for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. Both algorithms, called Alg-Neighbors and Alg-Edges, make use of biased and unbiased dice having faces, and are analyzed in terms of correctness, expected time complexity and rate of convergence. First, the Alg-Neighbors algorithm is presented as a generalization of the Calabrese/França algorithm for dice (or coins) with 2 faces. It is proved that a convenient biasing function applied to all dice changes the expected time complexity from sub-exponential, i.e., (for unbiased dice with faces), to , where is the number of the system’s nodes. Next, it is shown that the Alg-Edges algorithm is able to produce acyclic orientations in steps with high probability, where denotes the total number of edges. Finally, a speed of convergence versus quality of acyclic orientation generation (associated number of colors) tradeoff is identified between Alg-Neighbors and Alg-Edges algorithms. Computational experiments were carried out in order to provide a more accurate description of the behavior of both algorithms. [Copyright &y& Elsevier]