# 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

## Access Full Article

top## Abstract

top## How to cite

topSzachniuk, 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] 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] 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). Zbl1201.90001MR1205775
- [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] J. Bang-Jensen, G. Gutin, Properly colored hamiltonian paths in edge-coloured complete graphs. Disc. Appl. Math.82 (1998) 247–250. Zbl0897.05037MR1609957
- [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. Zbl0868.90128
- [8] D.P. Bertsekas, Network Optimization: Continuous and Discrete Models. Athena Scientific (1998). Zbl0997.90505
- [9] J. Bialogrodzki, Path coloring and routing in graphs, in Contemporary Mathematics, edited by M. Kubale. American Mathematical Society (2004) 139–152. MR2076995
- [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. Bioinformatics21 (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). Zbl0688.05016MR536131
- [14] B. Bollobás, P. Erdos, Alternating hamiltonian cycles. Isr. J. Math.23 (1976) 126–131. Zbl0325.05114MR411999
- [15] J.A. Bondy, U.S.R Murty, Graph Theory with Applications, Macmillan Press, London (1976). Zbl1226.05083MR411988
- [16] F. Carrabs, R. Cerulli, M. Gentili, The Labeled Maximum Matching Problem. Comput. Oper. Res.36 (2009) 1859–1867. Zbl1179.90318MR2586270
- [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] 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. Zbl0954.90057MR1700145
- [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] M.C. De Cola, G. Felici, M. Szachniuk, The Orderly Colored Longest Path Problem. CNR-IASI Technical Report 29 (2012). Zbl1288.90117
- [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] D. Dorninger, Hamiltonian circuits determining the order of chromosomes. Disc. Appl. Math.50 (1994) 159–168. Zbl0823.92010MR1275419
- [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] 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. Zbl0605.90123MR830485
- [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] 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] M. Kchikech, O. Togni, Paths coloring algorithms in mesh networks. Lect. Not. Comput. Sci. (2003) 193–202. Zbl1038.68944MR2062218
- [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. Zbl1214.05059
- [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. Zbl0819.05039MR1318749
- [34] B.R. Myers, Enumeration of tour in hamiltonian rectangular lattice graphs. Math. Mag.54 (1981) 19–23. Zbl0456.05035MR605274
- [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. Algorithmica13 (1995) 77-105. Zbl0840.92011MR1304310
- [37] P.A. Pevzner, Computational Molecular Biology: an algorithmic approach. MIT Press (2000). Zbl0972.92011MR1790966
- [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. Heuristics19 (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. Zbl1306.05075
- [44] S. Szeider, Finding paths in graphs avoiding forbidden transitions. Disc. Appl. Math.126 (2003) 239–251. Zbl1010.68099MR1948216
- [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. Zbl1260.68306MR2817080
- [47] J.J. Watkins, R.L. Hoenigman, Knight’s tours on a torus. Mathematics70 (1997) 175–184. Zbl0906.05041MR1456114
- [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] A. Yeo, A note on alternating cycles in edge-colored graphs. J. Comb. Theor. B69 (1997) 222–225. Zbl0870.05042MR1438622
- [50] http://prolland.free.fr/works/research/dsat/dimacs.html.

## NotesEmbed ?

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