Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results

A. Benkouar; Y. Manoussakis; V. Th. Paschos; R. Saad

RAIRO - Operations Research - Recherche Opérationnelle (1996)

  • Volume: 30, Issue: 4, page 417-438
  • ISSN: 0399-0559

How to cite

top

Benkouar, A., et al. "Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results." RAIRO - Operations Research - Recherche Opérationnelle 30.4 (1996): 417-438. <http://eudml.org/doc/105137>.

@article{Benkouar1996,
author = {Benkouar, A., Manoussakis, Y., Paschos, V. Th., Saad, R.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {NP-completeness; edge-colored graph; alternating factors; alternating Hamiltonian cycles; polynomial characterization},
language = {eng},
number = {4},
pages = {417-438},
publisher = {EDP-Sciences},
title = {Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results},
url = {http://eudml.org/doc/105137},
volume = {30},
year = {1996},
}

TY - JOUR
AU - Benkouar, A.
AU - Manoussakis, Y.
AU - Paschos, V. Th.
AU - Saad, R.
TI - Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 4
SP - 417
EP - 438
LA - eng
KW - NP-completeness; edge-colored graph; alternating factors; alternating Hamiltonian cycles; polynomial characterization
UR - http://eudml.org/doc/105137
ER -

References

top
  1. 1. M. BÁNKFALVI and Z. BÁNKFALVI, Alternating Hamiltonian Circuit in Two-Colored Complete Graphs, Theory of Graphs, Proc. Colloq. Tihany, Academic Press, New York, 1968, pp. 11-18. Zbl0159.54202MR233731
  2. 2. A. BENKOUAR, Y. MANOUSSAKIS and R. SAAD, Alternating Cycles through Given Vertices in Edge-Colored Complete Graphs, to appear in J. of Comb. Comput. and Comb. Maths. Zbl0813.05042
  3. 3. A. BENKOUAR, Y. MANOUSSAKIS and R. SAAD, Edge-Colored Complete Graphs Containing Alternating Hamiltonian Cycles, submitted. Zbl1017.05068
  4. 4. B. BOLLOBAS and P. ERDÖS, Alternating Hamiltonian Cycles, Israël Journal of Mathematics, 1976, 23, pp. 126-131. Zbl0325.05114MR411999
  5. 5. A. BONDY and U. S. R. MURTY, Graph Theory with Applications, McMillan Press, 1976. Zbl1226.05083
  6. 6. C. C. CHEN and D. E. DAYKIN, Graphs with Hamiltonian Cycles having Adjacent Lines Different Colors, J. Combinatorial Theory (B), 1976, 21, pp. 135-139. Zbl0287.05106MR422070
  7. 7. S. EVEN and O. KARIV, An O (n2.5) algorithm for Maximum Matching in General Graphs, Proc. 16th FOCS, 1975, pp. 100-112. MR428780
  8. 8. H. FLEISHNER, Eulerian Graphs and Related Topics, Series Book of the Annals of Discrete Mathematics, North-Holland, 1990. Zbl0792.05091
  9. 9. S. FORTUNE, J. HOPCROFT and J. WYLLIE, The Directed Subgraph Homeomorphism Problem, Theoretical Computer Science, 1980, 10, pp. 111-121. Zbl0419.05028MR551599
  10. 10. M. R. GAREY and D. S. JOHNSON, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. Zbl0411.68039MR519066
  11. 11. P. HELL, Y. MANOUSSAKIS and Zs. TUZA, Packing Problems in Edge Colored Complete Graphs, to appear in Discrete Applied Mathematics, 1994. Zbl0806.05054MR1287979
  12. 12. Y. MANOUSSAKIS, A Linear Algorithm for Finding Hamiltonian Cycles in Tournaments, Discrete Applied Mathematics, 1992, 36(2), pp. 199-201. Zbl0776.05095MR1165836
  13. 13. Y. MANOUSSAKIS, Alternating Paths in Edge-Colored Complete Graphs, to appear in Discrete Applied Mathematics, 1994. Zbl0819.05039MR1318749
  14. 14. Y. MANOUSSAKIS, O. MEGALAKAKI, M. SPYRATOS, WUN-SENG CHOU and Z. TUZA, Alternating Paths Through Given Vertices in Edge-Colored Graphs, submitted. Zbl0826.68064
  15. 15. Y. MANOUSSAKIS, M. SPYRATOS and Z. TUZA, Cycles and Paths with Given Color Patterns, submitted. Zbl0839.05056
  16. 16. Y. MANOUSSAKIS and Z. TUZA, Polynomial Algorithms for Finding Cycles and Paths in Bipartite Tournaments, SIAM J. on Discrete Mathematics, 1990, 3, pp. 537-543. Zbl0715.05042MR1069112

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.