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

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.


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
Full Text: DOI


[1] Aho, A.; Hopcroft, J.; Ullman, J., Data Structures and Algorithms (1983), Addison-Wesley: Addison-Wesley Reading, MA
[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
[7] Bollodas, R.; Erdös, P., Alternating hamiltonian cycles, Israel J. Math., 23, 126-130 (1976)
[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
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.