Alternating Path of length L in c- edges colored graphs
Keywords:
c-edgecolored, dynamic algorithm,paths and cycles of length of k, alternating pathAbstract
A graph G: = (V, E) is called c-edge colored if and only if there exists a mapping A between the set E (G), the edge set in the graph G, and a set C of colors, such that |C| = c, and A maps a color c in C to every edge e? E(G)|. A path P in a c-edge colored graph is called an alternating path if two adjacent edges of P differ in color.
We propose a dynamic algorithm, which resolves the following problem:
- Find an alternating path of length L in a c-edge colored complete graph between two given vertices s, t ? V (G).
Besides we show that the proved results for c = 2 in [2] for the xy-path is also true for c > 2. Thus we generalize these results. We also deal with the problem of the (s, t) –Cycles, for 2-edge colored presented in [7], in a c-edge colored graph with c > 2. We propose another algorithm that finds in polynomial time the set of all paths and cycles of length of k, where k = log (n) and n is the order of the graph G. Further, a method to find in polynomial time the set of all paths and cycles of length of k within a c-edge colored graph, where log(n) < k ? n.
We also consider the problem to determine the length of a shortest path between two given vertices in c-edge colored complete graph. In this paper, we therefore deal with the following question:
- Under which conditions can it be possible to reduce in a graph G the length of a given path between two vertices such as the path remains alternating between the two vertices?
In another paper we will deal with the minimal length of such path.
The resolution of this question obliges us to consider the different classes of graphs to find the necessary and sufficient conditions to attain such goal.
References
2. Manoussakis Y. Alternating paths in edge-coloured complete graphs. Discrete Applied Mathematics 1995; 56(2&3): 297 – 309.
3. Bang-Jensen J, Denmark GG. Alternating cycles and paths in edge-coloured multigraphs: A survey. Discrete Mathematics 1997; 165/166: 39-60.
4. Goddyn L. Edmonds’ Minimum Weight Perfect Matching Algorithm. Math 408.
5. Hansdsome Non-Commutative Proof-Nets: perfect matchings, series-parallel order and Hamilton circuit Sylvain Pogodalla- Christian Retoré Rapport de recherche N° 5409 Dec. 2004 INRIA.
6. On Path of Length L In C- Edges Colored Graphs. Chou WS, Manoussakis Y, Megalakaki O et al. Tuza Math Inf Sci Hum 199; 32(127): 49-58.
7. Manoussakis Y, Spyratos M, Tuza Zs. Cycles of given Color Patterns. Journal of graph theory 1996; 21(2): 153-162.
8. Alon N, Yuster R, Zwick U. Color-Coding. J ACM 1995; 42: 844-856.
9. Scott J, Ideker T, Karp RM et al. Efficient Algorithmus for Detecting Signaling Pathways in Protein Interaction Networks. LNCS 2005; 3500: 1-13.
10. Robertson N Seymour P. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms 1986; 7: 309-322.
11. Feng J, Giesen HE, Guo Y et al. Characterization of edge-colored complete graphs with properly colored Hamilton paths. Journal of Graph Theory 2006; 53: 333-346.
12. Szeider S. Finding paths in graphs avoiding transitions. Discrete Applied Mathematics 2003; 126(2&3): 239251.
