The Orderly Colored Longest Path Problem - a survey of applications and new algorithms (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• The Orderly Colored Longest Path Problem - a survey of applications and new algorithms (Articolo in rivista) (literal)

Anno

• 2014-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1051/ro/2013046 (literal)

Alternative label

• M. Szachniuk, M.C. De Cola, G. Felici, J. Blazewicz (2014)
  The Orderly Colored Longest Path Problem - a survey of applications and new algorithms
  in RAIRO. Recherche opérationnelle
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• M. Szachniuk, M.C. De Cola, G. Felici, J. Blazewicz (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 48 (literal)

Rivista

• RAIRO. Recherche opérationnelle (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo

• 1 (literal)

Note

• ISI Web of Science (WOS) (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland. mszachniuk@cs.put.poznan.pl Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland; mszachniuk@cs.put.poznan.pl; jblazewicz@cs.put.poznan.pl IRCCS Centro Neurolesi \"Bonino Pulejo\", S.S. 113 Via Palermo c/da Casazza, 98123 Messina, Italy; cristina.decola@gmail.com Institute of Systems Analysis and Computer Science \"A. Ruberti\", National Research Council, V.le Manzoni 30, 00185 Rome, Italy; giovanni.felici@iasi.cnr.it (literal)

Titolo

• The Orderly Colored Longest Path Problem - a survey of applications and new algorithms (literal)

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. (literal)

Prodotto di

• Ottimizzazione e modellistica matematica in biologia (INT.P02.003.001) (Modulo)
• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)

Autore CNR

• GIOVANNI FELICI (Unità di personale interno)

Incoming links:

Autore CNR di

• GIOVANNI FELICI (Unità di personale interno)

Prodotto

• Istituto di analisi dei sistemi ed informatica \"Antonio Ruberti\" (IASI) (Istituto)
• Ottimizzazione e modellistica matematica in biologia (INT.P02.003.001) (Modulo)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• RAIRO. Recherche opérationnelle (Rivista)