zbMATH — the first resource for mathematics

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 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, (), 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, (), 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. · Zbl 0813.05042
[6] 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)
[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(n2.5) algorithm for maximum matchings in general graphs, (), 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 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, () · Zbl 0618.05001
[15] N. Robertson and P.D. Seymour, On graph minors XIII, The disjoint path problem, to appear. · Zbl 0823.05038
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.