Alternating paths in edge-colored complete graphs. (English) Zbl 0819.05039

Manoussakis, Y.

Discrete Appl. Math. 56, No. 2-3, 297-309 (1995).

An alternating path in an edge-colored graph is a path in which every two adjacent edges have different colors. In this paper, an \(O(n^{2.5})\) algorithm is given for finding the maximum number of internally vertex- disjoint alternating paths between a specified pair of vertices in an edge-colored complete graph. Related problems are studied in which further restrictions on the paths and on the edge-colorings are imposed.

Reviewer: C.J.Colbourn (Waterloo / Ontario)

MSC:

05C38	Paths and cycles
05C15	Coloring of graphs and hypergraphs
68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity

Keywords:

NP-completeness; alternating path; edge-colored graph; algorithm; complete graph; edge-colorings

References:

[1]	Aho, A.; Hopcroft, J.; Ullman, J., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0487.68005
[2]	Alt, H.; Blum, N.; Mehlhorn, K.; Paul, M., Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{32}(m/log n)^{12})\), Inform. Process. Lett., 37, 237-240 (1991) · Zbl 0714.68036
[3]	Bankfalvi, M.; Bankfalvi, Z., Alternating circuit in two-colored complete graphs, (Proceedings Colloquium Tihany 1968 (1968), Academic Press: Academic Press New York), 11-18 · Zbl 0159.54202
[4]	Benkouar, A.; Manoussakis, Y.; Paschos, V.; Saad, R., On the complexity of Hamiltonian and Eulerian problems in edge-colored complete graphs, (Lecture Notes in Computer Science, 557 (1991), Springer: Springer Berlin), 190-198 · Zbl 0868.90128
[5]	A. Benkouar, Y. Manoussakis and R. Saad, Alternating cycles through fixed vertices in edge-colored graphs, J. Combin. Math. Combin. Comput., to appear.; A. Benkouar, Y. Manoussakis and R. Saad, Alternating cycles through fixed vertices in edge-colored graphs, J. Combin. Math. Combin. Comput., to appear. · Zbl 0813.05042
[6]	A. Benkouar, Y. Manoussakis and R. Saad, Edge-colored complete graphs containing alternating hamiltonian cycles, submitted.; A. Benkouar, Y. Manoussakis and R. Saad, Edge-colored complete graphs containing alternating hamiltonian cycles, submitted. · Zbl 1017.05068
[7]	Bollodas, R.; Erdös, P., Alternating hamiltonian cycles, Israel J. Math., 23, 126-130 (1976) · Zbl 0325.05114
[8]	Chen, C. C.; Daykin, D. E., Graph with hamiltonian cycles having adjacent lines different colors, J. Combin. Theory Ser. B, 21, 135-139 (1976) · Zbl 0287.05106
[9]	Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[10]	Even, S.; Kariv, O., An \(O(n^{2.5})\) algorithm for maximum matchings in general graphs, (Proceedings of the 16th Annual Symposium on Foundations of Computer Science. Proceedings of the 16th Annual Symposium on Foundations of Computer Science, Berkeley, CA, 1975 (1975), IEEE Computer Society Press: IEEE Computer Society Press New York), 100-112
[11]	Fortune, S.; Hopcroft, J.; Wyllie, J., The directed subgraph homeomorphism problem, Theoret. Comput. Sci., 10, 111-121 (1980) · Zbl 0419.05028
[12]	Garey, M.; Johnson, D., Computers and Intractability — A Guide to the Theory of NP-Complete-ness (1979), Freeman: Freeman New York · Zbl 0411.68039
[13]	Hell, P.; Manoussakis, Y.; Tuza, Zs., Packing problems in edge-colored graphs, Discrete Appl. Math., 52, 295-306 (1994) · Zbl 0806.05054
[14]	Lovasz, L.; Plummer, M., Matching Theory, (North-Holland Mathematics Studies (1986), North-Holland: North-Holland Amsterdam) · Zbl 0618.05001
[15]	N. Robertson and P.D. Seymour, On graph minors XIII, The disjoint path problem, to appear.; N. Robertson and P.D. Seymour, On graph minors XIII, The disjoint path problem, to appear. · Zbl 0823.05038