The Orderly Colored Longest Path Problem – a survey of applications and new algorithms

Marta Szachniuk; Maria Cristina De Cola; Giovanni Felici; Jacek Blazewicz

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

  • Volume: 48, Issue: 1, page 25-51
  • ISSN: 0399-0559

Abstract

top
A concept of an Orderly Colored Longest Path (OCLP) refers to the problem of finding the longest path in a graph whose edges are colored with a given number of colors, under the constraint that the path follows a predefined order of colors. The problem has not been widely studied in the previous literature, especially for more than two colors in the color arrangement sequence. The recent and relevant application of OCLP is related to the interpretation of Nuclear Magnetic Resonance experiments for RNA molecules. Besides, an employment of this specific graph model can be found in transportation, games, and grid graphs. OCLP models the relationships between consecutive edges of the path, thus it appears very useful in representing the real problems with specific ties between their components. In the paper, we show OCLP’s correlation with similar issues known in graph theory. We describe the applications, three alternative models and new integer programming algorithms to solve OCLP. They are formulated by means of max flow problems in a directed graph with packing constraints over certain partitions of nodes. The methods are compared in a computational experiment run for a set of randomly generated instances.

How to cite

top

Szachniuk, Marta, et al. "The Orderly Colored Longest Path Problem – a survey of applications and new algorithms." RAIRO - Operations Research - Recherche Opérationnelle 48.1 (2014): 25-51. <http://eudml.org/doc/275060>.

@article{Szachniuk2014,
abstract = {A concept of an Orderly Colored Longest Path (OCLP) refers to the problem of finding the longest path in a graph whose edges are colored with a given number of colors, under the constraint that the path follows a predefined order of colors. The problem has not been widely studied in the previous literature, especially for more than two colors in the color arrangement sequence. The recent and relevant application of OCLP is related to the interpretation of Nuclear Magnetic Resonance experiments for RNA molecules. Besides, an employment of this specific graph model can be found in transportation, games, and grid graphs. OCLP models the relationships between consecutive edges of the path, thus it appears very useful in representing the real problems with specific ties between their components. In the paper, we show OCLP’s correlation with similar issues known in graph theory. We describe the applications, three alternative models and new integer programming algorithms to solve OCLP. They are formulated by means of max flow problems in a directed graph with packing constraints over certain partitions of nodes. The methods are compared in a computational experiment run for a set of randomly generated instances.},
author = {Szachniuk, Marta, Cristina De Cola, Maria, Felici, Giovanni, Blazewicz, Jacek},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {edge colored graph; longest path problem; alternating path},
language = {eng},
number = {1},
pages = {25-51},
publisher = {EDP-Sciences},
title = {The Orderly Colored Longest Path Problem – a survey of applications and new algorithms},
url = {http://eudml.org/doc/275060},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Szachniuk, Marta
AU - Cristina De Cola, Maria
AU - Felici, Giovanni
AU - Blazewicz, Jacek
TI - The Orderly Colored Longest Path Problem – a survey of applications and new algorithms
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 1
SP - 25
EP - 51
AB - A concept of an Orderly Colored Longest Path (OCLP) refers to the problem of finding the longest path in a graph whose edges are colored with a given number of colors, under the constraint that the path follows a predefined order of colors. The problem has not been widely studied in the previous literature, especially for more than two colors in the color arrangement sequence. The recent and relevant application of OCLP is related to the interpretation of Nuclear Magnetic Resonance experiments for RNA molecules. Besides, an employment of this specific graph model can be found in transportation, games, and grid graphs. OCLP models the relationships between consecutive edges of the path, thus it appears very useful in representing the real problems with specific ties between their components. In the paper, we show OCLP’s correlation with similar issues known in graph theory. We describe the applications, three alternative models and new integer programming algorithms to solve OCLP. They are formulated by means of max flow problems in a directed graph with packing constraints over certain partitions of nodes. The methods are compared in a computational experiment run for a set of randomly generated instances.
LA - eng
KW - edge colored graph; longest path problem; alternating path
UR - http://eudml.org/doc/275060
ER -

References

top
  1. [1] A. Abouelaoualim, K.Ch. Das, L. Faria, Y. Manoussakis, C. Martinhon, R. Saad, Paths and trails in edge-colored graphs. Theor. Comput. Sci.409 (2008) 497–510. Zbl1155.68053MR2473924
  2. [2] R.W. Adamiak, J. Blazewicz, P. Formanowicz, Z. Gdaniec, M. Kasprzak, M. Popenda, M. Szachniuk, An algorithm for an automatic NOE pathways analysis of 2D NMR spectra of RNA duplexes. J. Comput. Biol.11 (2004) 163–179. 
  3. [3] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, New Jersey (1993). Zbl1201.90001MR1205775
  4. [4] J. Bang-Jensen, G. Gutin, Alternating cycles and trails in 2-edge-colored complete multigraphs. Disc. Math.188 (1998) 61–72. Zbl0956.05040MR1630418
  5. [5] J. Bang-Jensen, G. Gutin, Properly colored hamiltonian paths in edge-coloured complete graphs. Disc. Appl. Math.82 (1998) 247–250. Zbl0897.05037MR1609957
  6. [6] B. Beauquier, S. Perennes and M. Syska, Efficient access to optical bandwidth routing and grooming in WDM networks: state-of-the-art survey. RESCCO Report IST-2001-33135, Universite de Nice-Sophia Antipolis (2002). 
  7. [7] A. Benkouar, Y.G. Manoussakis, V.Th. Paschos and R. Saad, On the complexity of some hamiltonian and eulerian problems in edge-colored complete graphs. Lect. Not. Comput. Sci.557 (1991) 190–198. Zbl0868.90128
  8. [8] D.P. Bertsekas, Network Optimization: Continuous and Discrete Models. Athena Scientific (1998). Zbl0997.90505
  9. [9] J. Bialogrodzki, Path coloring and routing in graphs, in Contemporary Mathematics, edited by M. Kubale. American Mathematical Society (2004) 139–152. MR2076995
  10. [10] J. Blazewicz, M. Szachniuk and A. Wojtowicz, Evolutionary approach to NOE paths assignment in RNA structure elucidation. Proceedings of the 2004 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (2004) 206–213. 
  11. [11] J. Blazewicz, M. Szachniuk, A. Wojtowicz, RNA tertiary structure determination: NOE pathways construction by tabu search. Bioinformatics21 (2005) 2356–2361. 
  12. [12] J. Blazewicz, P.L. Hammer, P. Lukasiak, Predicting secondary structures of proteins. IEEE Eng. Med. Biol. Mag.24 (2005) 88–94. 
  13. [13] B. Bollobás, Graph Theory. An Introductory Course, Springer-Verlag, New York (1979). Zbl0688.05016MR536131
  14. [14] B. Bollobás, P. Erdos, Alternating hamiltonian cycles. Isr. J. Math.23 (1976) 126–131. Zbl0325.05114MR411999
  15. [15] J.A. Bondy, U.S.R Murty, Graph Theory with Applications, Macmillan Press, London (1976). Zbl1226.05083MR411988
  16. [16] F. Carrabs, R. Cerulli, M. Gentili, The Labeled Maximum Matching Problem. Comput. Oper. Res.36 (2009) 1859–1867. Zbl1179.90318MR2586270
  17. [17] R. Cerulli, A. Fink, M. Gentili, S. Voss, Metaheuristics comparison for the minimum labelling spanning tree problem, in The Next Wave on Computing, Optimization, and Decision Technologies, edited by B.L. Golden, S. Raghavan and E.A. Wasil. Springer, New York (2005) 93–106. Zbl1179.90007
  18. [18] R. Cerulli, A. Fink, M. Gentili, S. Voss, Extensions of the Minimum Labelling Spanning Tree Problem. J. Telecom. Inform. Technol.4 (2006) 39–45. 
  19. [19] B.V. Cherkassky, A.V. Goldberg, Negative-cycle detection algorithms. Math. Prog.85 (1999) 277–311. Zbl0954.90057MR1700145
  20. [20] W.S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, Zs. Tuza, Paths through fixed vertices in edge-colored graphs. Mathematiques, Informatique et Sciences Humaines 127 (1994) 49–58. Zbl0826.68064MR1324227
  21. [21] M.C. De Cola, G. Felici, M. Szachniuk, The Orderly Colored Longest Path Problem. CNR-IASI Technical Report 29 (2012). Zbl1288.90117
  22. [22] A. Conrad, T. Hindrichs, H. Morsy, I. Wegener, Solution of the Knight’s Hamiltonian Path Problem on Chessboards. Disc. Appl. Math.50 (1994) 125–134. Zbl0793.68113MR1275416
  23. [23] D. Dorninger, Hamiltonian circuits determining the order of chromosomes. Disc. Appl. Math.50 (1994) 159–168. Zbl0823.92010MR1275419
  24. [24] J. Feng, H.-E. Giesen, Y. Guo, G. Gutin, T. Jensen, A. Rafiey, Characterization of edge-colored complete graphs with properly colored hamiltonian paths. J. Graph Theor.53 (2006) 333–346. Zbl1125.05037MR2270727
  25. [25] P. Festa, The shortest path tour problem: problem definition, modeling, and optimization. Proceedings of INOC’2009 (2009) 1–7. 
  26. [26] G. Gallo, S. Pallottino, Shortest path methods: a unifying approach. Math. Program. Stud.26 (1986) 38–64. Zbl0605.90123MR830485
  27. [27] M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness. W.H. Freeman & Co., San Francisco CA (1979). Zbl0411.68039MR519066
  28. [28] L. Gourvès, A. Lyra, C. Martinhon, J. Monnot, F. Protti, On s-t paths and trails in edge-colored graphs. Electron. Notes Discrete Math.35 (2009) 221–226. Zbl1268.05112MR2579434
  29. [29] M. Kchikech, O. Togni, Paths coloring algorithms in mesh networks. Lect. Not. Comput. Sci. (2003) 193–202. Zbl1038.68944MR2062218
  30. [30] A. Kosowski, Path assignment with wavelength constraints. Ph.D. Thesis, Gdansk University of Technology, Poland (2006). 
  31. [31] H. Li, G. Wang, S. Zhou, Long alternating cycles in edge-colored complete graphs. Lect. Not. Comput. Sci.4613 (2007) 305–309. Zbl1214.05059
  32. [32] F. Luccio, C. Mugnia, Hamiltonian paths on a rectangular chess-board. Proceedings of 16th Annual Allerton Conference (1978) 161–173. 
  33. [33] Y. Manoussaskis, Alternating paths in edge-colored complete graphs. Disc. Appl. Math.56 (1995) 297–309. Zbl0819.05039MR1318749
  34. [34] B.R. Myers, Enumeration of tour in hamiltonian rectangular lattice graphs. Math. Mag.54 (1981) 19–23. Zbl0456.05035MR605274
  35. [35] C. Nomikos, Coloring in Graphs, Ph.D. Thesis, Dept.of Electrical and Computer Engineering, National Technical University of Athens, Greece (1997). 
  36. [36] P.A. Pevzner, DNA physical mapping and alternating eulerian cycles in colored graphs. Algorithmica13 (1995) 77-105. Zbl0840.92011MR1304310
  37. [37] P.A. Pevzner, Computational Molecular Biology: an algorithmic approach. MIT Press (2000). Zbl0972.92011MR1790966
  38. [38] M. Popenda, M. Szachniuk, M. Antczak, K.J. Purzycka, P. Lukasiak, N. Bartol, J. Blazewicz, R.W. Adamiak, Automated 3D structure composition for large RNAs. Nucleic Acids Res. 40 (2012) e112. 
  39. [39] M. Popenda, M. Blazewicz, M. Szachniuk, R.W. Adamiak, RNA FRABASE version 1.0: an engine with a database to search for the three-dimensional fragments within RNA structures. Nucleic Acids Res. 36 (2008) D386-D391. 
  40. [40] M. Popenda, M. Szachniuk, M. Blazewicz, S. Wasik, E.K. Burke, J. Blazewicz, R.W. Adamiak, RNA FRABASE 2.0: an advanced web-accessible database with the capacity to search the three-dimensional fragments within RNA structures. BMC Bioinformatics11 (2010) 231. 
  41. [41] M. Szachniuk, M. Popenda, R.W. Adamiak, J. Blazewicz, An assignment walk through 3D NMR spectrum. Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (2009) 215–219. 
  42. [42] M. Szachniuk, M. Malaczynski, E. Pesch, E.K. Burke, J. Blazewicz, MLP accompanied beam search for the resonance assignment problem. J. Heuristics19 (2013) 443–464. 
  43. [43] M. Szachniuk, M.C. De Cola, G. Felici, D. de Werra, J. Blazewicz, Optimal pathway reconstruction on 3D NMR maps. Disc. Appl. Math. (2013) submitted for publication. Zbl1306.05075
  44. [44] S. Szeider, Finding paths in graphs avoiding forbidden transitions. Disc. Appl. Math.126 (2003) 239–251. Zbl1010.68099MR1948216
  45. [45] I.L. Tseng, H.W. Chen, C.I. Lee, Obstacle-aware longest path routing with parallel MILP solvers. Proceedings of WCECS (2010). 
  46. [46] Y. Wang, Y. Desmedt, Edge-colored graphs with applications to homogeneous faults. Inf. Proc. Lett.111 (2011) 634–641. Zbl1260.68306MR2817080
  47. [47] J.J. Watkins, R.L. Hoenigman, Knight’s tours on a torus. Mathematics70 (1997) 175–184. Zbl0906.05041MR1456114
  48. [48] T. Zok, M. Popenda, M. Szachniuk, MCQ4Structures to compute similarity of molecule structures. Central Eur. J. Oper. Res. (2013), doi:10.1007/s10100-013-0296-5. MR3231038
  49. [49] A. Yeo, A note on alternating cycles in edge-colored graphs. J. Comb. Theor. B69 (1997) 222–225. Zbl0870.05042MR1438622
  50. [50] http://prolland.free.fr/works/research/dsat/dimacs.html. 

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.