zbMATH — the first resource for mathematics

Exact approaches for the orderly colored longest path problem: performance comparison. (English) Zbl 06988110
Summary: In this paper, we consider a particular graph-optimization problem. Given an edge-colored graph and a set of constraints on the sequence of the colors, one is to find the longest path whose colored edges obey the constraints on the sequence of the colors. In the actual formulation, the problem generalizes already known NP-Complete problems, and, evidently, the alternating path problem in edge colored graphs. Recent literature has shown several contexts where such problem may be useful to model interesting applications, and has proposed exact IP models and related algorithms. We extend on these existing models and extensively test new formulations for the problem, showing how one of the newly developed model clearly exhibits better performance, allowing to solve at optimality instances of significant sizes.
90B Operations research and management science
Full Text: DOI
[1] Abouelaoualim, A.; Das, K. Ch.; de la Vega, W. F.; Karpinski, M.; Manoussakis, Y.; Martinhon, C. A.; Saad, R., Cycles and paths in edge-colored graphs with given degrees, J. Graph Theory, 64, 63-86, (2010) · Zbl 1202.05067
[2] Adamiak, R. W.; Blazewicz, J.; Formanowicz, P.; Gdaniec, Z.; Kasprzak, M.; Popenda, M.; Szachniuk, M., An algorithm for an automatic (NOE) pathways analysis of 2D NMR spectra of RNA dueplexes, J. Comput. Biol., 11, 163-179, (2004)
[3] Benkouar, A.; Manoussakis, Y.; Paschos, V.; Saad, R., On the complexity of finding alternating Hamiltonian and Eulerian cycles in edge-coloured graphs, Lecture Notes Comput. Sci., 557, 190-198, (1991)
[4] Blazewicz, J.; Szachniuk, M.; Wojtowicz, A., RNA tertiary structure determination: NOE pathways construction by tabu search, Bioinformatics, 21, 10, 2356-2361, (2005)
[5] Brimberg, J.; Mladenovic, N.; Urosevic, D.; Ngai, E., Variable neighborhood search for the heaviest k-subgraph, Comput. Oper. Res., 36, 11, 2885-2891, (2009) · Zbl 1162.90540
[6] Carrabs, F.; Cerrone, C.; Cerulli, R.; Silvestri, S., On the complexity of rainbow spanning forest problem, Optim. Lett., 12, 3, 443-454, (2018) · Zbl 1400.90256
[7] Carrabs, F.; Cerrone, C.; Cerulli, R.; Silvestri, S., The rainbow spanning forest problem, Soft. Comput., 22, 8, 2765-2776, (2018) · Zbl 1398.90132
[8] Dorninger, D., Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 50, 159-168, (1994) · Zbl 0823.92010
[9] Festa, P., The shortest path tour problem: problem definition, modeling, and optimization, Proceedings of INOC’2009, vol. 217, 1-7, (2009)
[10] Fujita, S.; Magnant, C., Properly colored paths and cycles, Discrete Appl. Math., 159, 1391-1397, (2011) · Zbl 1228.05150
[11] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, Vol. 217, (1979), Freeman & Co. San Francisco CA · Zbl 0411.68039
[12] Lo, A., A Dirac type condition for properly coloured paths and cycles, J. Graph Theory, 76, 60-87, (2014) · Zbl 1294.05077
[13] Lo, A., An edge-coloured version of dirac’s theorem, SIAM J. Discrete Math., 28, 18-36, (2014) · Zbl 1297.05085
[14] Padberg, M. W.; Rao, M. R., Odd minimum cut-sets and b-matchings, Math. Oper. Res., 7, 1, 67-80, (1982) · Zbl 0499.90056
[15] Pevzner, P. A., DNA physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica, 13, 77-105, (1995) · Zbl 0840.92011
[16] Szachniuk, M.; De Cola, M. D.; Felici, G.; Blazewicz, J., The orderly colored longest path problem - a survey of applications and new algorithms, RAIRO - Oper. Res., 48, 25-51, (2014) · Zbl 1288.90117
[17] Szachniuk, M.; De Cola, M. D.; Felici, G.; Blazewicz, J.; de Werra, D., Optimal pathway reconstruction on 3D NMR maps, Discrete Appl. Math., 182, 134-149, (2014) · Zbl 1306.05075
[18] Szachniuk, M.; Popenda, M.; Adamiak, R. W.; Blazewicz, J., An assignment walk through 3D NMR spectrum, Proceedings of IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, 215-219, (2009)
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.