The Orderly Colored Longest Path Problem - a survey of applications and new algorithms
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 1, pp. 25-51.

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.

DOI : 10.1051/ro/2013046
Classification : 90C35, 94C15, 97K30
Mots-clés : edge colored graph, longest path problem, alternating path 
@article{RO_2014__48_1_25_0,
     author = {Szachniuk, Marta and Cristina De Cola, Maria and Felici, Giovanni and Blazewicz, Jacek},
     title = {The {Orderly} {Colored} {Longest} {Path} {Problem} - a survey of applications and new algorithms},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {25--51},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     doi = {10.1051/ro/2013046},
     mrnumber = {3143767},
     zbl = {1288.90117},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2013046/}
}
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
SP  - 25
EP  - 51
VL  - 48
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2013046/
DO  - 10.1051/ro/2013046
LA  - en
ID  - RO_2014__48_1_25_0
ER  - 
%0 Journal Article
%A Szachniuk, Marta
%A Cristina De Cola, Maria
%A Felici, Giovanni
%A Blazewicz, Jacek
%T The Orderly Colored Longest Path Problem - a survey of applications and new algorithms
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2014
%P 25-51
%V 48
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2013046/
%R 10.1051/ro/2013046
%G en
%F RO_2014__48_1_25_0
Szachniuk, Marta; Cristina De Cola, Maria; Felici, Giovanni; Blazewicz, Jacek. The Orderly Colored Longest Path Problem - a survey of applications and new algorithms. RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 1, pp. 25-51. doi : 10.1051/ro/2013046. http://www.numdam.org/articles/10.1051/ro/2013046/

[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. | MR | Zbl

[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] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, New Jersey (1993). | MR | Zbl

[4] J. Bang-Jensen, G. Gutin, Alternating cycles and trails in 2-edge-colored complete multigraphs. Disc. Math. 188 (1998) 61-72. | MR | Zbl

[5] J. Bang-Jensen, G. Gutin, Properly colored hamiltonian paths in edge-coloured complete graphs. Disc. Appl. Math. 82 (1998) 247-250. | MR | Zbl

[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] 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. | DOI

[8] D.P. Bertsekas, Network Optimization: Continuous and Discrete Models. Athena Scientific (1998). | Zbl

[9] J. Bialogrodzki, Path coloring and routing in graphs, in Contemporary Mathematics, edited by M. Kubale. American Mathematical Society (2004) 139-152. | MR

[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] J. Blazewicz, M. Szachniuk, A. Wojtowicz, RNA tertiary structure determination: NOE pathways construction by tabu search. Bioinformatics 21 (2005) 2356-2361.

[12] J. Blazewicz, P.L. Hammer, P. Lukasiak, Predicting secondary structures of proteins. IEEE Eng. Med. Biol. Mag. 24 (2005) 88-94.

[13] B. Bollobás, Graph Theory. An Introductory Course, Springer-Verlag, New York (1979). | MR | Zbl

[14] B. Bollobás, P. Erdos, Alternating hamiltonian cycles. Isr. J. Math. 23 (1976) 126-131. | MR | Zbl

[15] J.A. Bondy, U.S.R Murty, Graph Theory with Applications, Macmillan Press, London (1976). | MR | Zbl

[16] F. Carrabs, R. Cerulli, M. Gentili, The Labeled Maximum Matching Problem. Comput. Oper. Res. 36 (2009) 1859-1867. | MR | Zbl

[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. | Zbl

[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] B.V. Cherkassky, A.V. Goldberg, Negative-cycle detection algorithms. Math. Prog. 85 (1999) 277-311. | MR | Zbl

[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. | Numdam | MR | Zbl

[21] M.C. De Cola, G. Felici, M. Szachniuk, The Orderly Colored Longest Path Problem. CNR-IASI Technical Report 29 (2012).

[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. | MR | Zbl

[23] D. Dorninger, Hamiltonian circuits determining the order of chromosomes. Disc. Appl. Math. 50 (1994) 159-168. | MR | Zbl

[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. | MR | Zbl

[25] P. Festa, The shortest path tour problem: problem definition, modeling, and optimization. Proceedings of INOC'2009 (2009) 1-7.

[26] G. Gallo, S. Pallottino, Shortest path methods: a unifying approach. Math. Program. Stud. 26 (1986) 38-64. | MR | Zbl

[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). | MR | Zbl

[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. | MR | Zbl

[29] M. Kchikech, O. Togni, Paths coloring algorithms in mesh networks. Lect. Not. Comput. Sci. (2003) 193-202. | MR | Zbl

[30] A. Kosowski, Path assignment with wavelength constraints. Ph.D. Thesis, Gdansk University of Technology, Poland (2006).

[31] H. Li, G. Wang, S. Zhou, Long alternating cycles in edge-colored complete graphs. Lect. Not. Comput. Sci. 4613 (2007) 305-309. | Zbl

[32] F. Luccio, C. Mugnia, Hamiltonian paths on a rectangular chess-board. Proceedings of 16th Annual Allerton Conference (1978) 161-173.

[33] Y. Manoussaskis, Alternating paths in edge-colored complete graphs. Disc. Appl. Math. 56 (1995) 297-309. | MR | Zbl

[34] B.R. Myers, Enumeration of tour in hamiltonian rectangular lattice graphs. Math. Mag. 54 (1981) 19-23. | MR | Zbl

[35] C. Nomikos, Coloring in Graphs, Ph.D. Thesis, Dept.of Electrical and Computer Engineering, National Technical University of Athens, Greece (1997).

[36] P.A. Pevzner, DNA physical mapping and alternating eulerian cycles in colored graphs. Algorithmica 13 (1995) 77-105. | MR | Zbl

[37] P.A. Pevzner, Computational Molecular Biology: an algorithmic approach. MIT Press (2000). | MR | Zbl

[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] 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] 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] 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] M. Szachniuk, M. Malaczynski, E. Pesch, E.K. Burke, J. Blazewicz, MLP accompanied beam search for the resonance assignment problem. J. Heuristics 19 (2013) 443-464.

[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.

[44] S. Szeider, Finding paths in graphs avoiding forbidden transitions. Disc. Appl. Math. 126 (2003) 239-251. | MR | Zbl

[45] I.L. Tseng, H.W. Chen, C.I. Lee, Obstacle-aware longest path routing with parallel MILP solvers. Proceedings of WCECS (2010).

[46] Y. Wang, Y. Desmedt, Edge-colored graphs with applications to homogeneous faults. Inf. Proc. Lett. 111 (2011) 634-641. | MR | Zbl

[47] J.J. Watkins, R.L. Hoenigman, Knight's tours on a torus. Mathematics 70 (1997) 175-184. | MR | Zbl

[48] T. Zok, M. Popenda, M. Szachniuk, MCQ4Structures to compute similarity of molecule structures. Central Eur. J. Oper. Res. (2013), doi: | DOI | MR

[49] A. Yeo, A note on alternating cycles in edge-colored graphs. J. Comb. Theor. B 69 (1997) 222-225. | MR | Zbl

[50] http://prolland.free.fr/works/research/dsat/dimacs.html.

Cité par Sources :