This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  2012, with author Felici G., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 12-29    

De Cola C, Giovanni Felici, Szachniuk M.

The Orderly Colored Longest Path Problem

ABSTRACT

We consider the problem of finding a longest path in a graph whose edges are colored with c colors, under the constraint that the edges of the path follow a given order of colors. The problem is referred to as the Orderly Colored Longest Path on a c-edge colored graph (OCLP). We show its relations with similar problems already studied and consider three alternative integer programming models for this problem. The three models are formulated by means of max flow problems on a directed graph with packing constraints over certain partitions of the nodes. This problem has not been modeled and studied in previous literature. A recent and relevant application is related with the interpretation of Nuclear Magnetic Resonance experiments. Besides, applications can be found in transportation, games, and grid graphs. The interestingness of this problem is motivated by the fact that it models the relations of consecutive edges of the path. All three integer programming formulations have been implemented and compared on a set of randomly generated instances.