A deeply studied research subject is the Shortest Path Problem. In particular, a new classification of the most studied algorithms and a wide experimentation have been proposed [GP86,GP88].
Auction-type algorithms have been introduced, which run in strongly polynomial time [BPS95,PS91,PS93]. The practical efficiency of sequential implementations has been extensively tested, and parallel impementations are being studied.
A new family of dual-ascent methods, called Hanging algorithms have been proposed and their efficiency is under investigation [PS97]. Hanging algorithms are used also in the Reoptimization context [NPS02].
Finally, the Dynamic Shortest Path Problem is a new research topic [PS98].

Another, quite promising, research activity concerns the study of directed hypergraphs, a generalization of directed graphs. The research is aimed at both the study of hypergraph properties [GLNP89,GLNP93,NPM94] and of optimization hypergraph problems such as shortest hyperpaths, minimum cuts and minimum cost hyperflows. In particular, a Simplex algorithm for the Minimum Cost Flow Problem on capacitated directed hypergraphs, based on the characterization of the basis structures in terms of spanning hypertrees, has been proposed [CGS92,CGS97,GLS96].

Furthermore, as it is pointed out in the Logical Inference and Optimization section, hypergraphs provide a powerful tool to model and solve a wide class of logical inference problems.

[NPS02] S. Nguyen, S. Pallottino and M.G. Scutellà "A new dual algorithm for shortest path reoptimization" Transportation and Nework Analysis - Current Trends, M. Gendreau e P. Marcotte eds., Kluwer, 221-235, 2002. (previously appeared as TR 99-14, Dipartimento di Informatica, Università di Pisa, 1999, revised July 2000)

[GS98a] G. Gallo, M.P. Scaparra "Routing with Minimum Fragmentation Cost" TR 06/98, Dip. di Informatica, Univ. di Pisa, 1998

[GS98b] G. Gallo, M.G. Scutellà "Minimum Makespan Assembly Problems" Working Paper, 1998 (submitted to Operations Research)

[PS98] S. Pallottino and M.G. Scutellà "Shortest path algorithms in transportation models: classical and innovative aspects" in (P. Marcotte and S. Nguyen, eds.) Equilibrium and Advanced Transportation Modelling, Kluwer, p.245-281, 1998

[S98] M.G. Scutellà "A strongly polynomial algorithm for the Uniform Balanced Network Flow Problem" Discrete Applied Mathematics 81, p. 123-131, 1998

[CGS97] R. Cambini, G. Gallo, M.G. Scutella' "Flows on Hypergraphs" Mathematical Programming 78, p. 195-217, 1997

[PS97] S.Pallottino and M.G.Scutellà "Dual algorithms for the shortest path tree problem" Networks 29, p. 125-133, 1997

[GLS96] G.Gallo, F. Licheri and M.G. Scutellà "The Hypergraph Simplex Approach: some experimental results" Ricerca Operativa 78, p. 21-54, 1996

[GS96] G. Gallo, M.G. Scutellà "Hyperflow Models" TR 26/96, Dip. di Informatica, Univ. di Pisa, 1996

[BPS95] D.P. Bertsekas, S. Pallottino and M.G. Scutellà "Polynomial Auction algorithms for shortest paths" Computational Optimization and Applications 4(2), p. 99-125, 1995

[GNS95] M. Gambale, M. Nonato and M.G. Scutellà "The Cutting Stock Problem: a new model based on hypergraph flows" Ricerca Operativa anno XXV, n.74, 1995

[GMM94] G.Gallo, F.Malucelli and M. Marrà: "Hamiltonian path algorithms for disk scheduling" TR 20/94, Dip. di Informatica, Univ. di Pisa, 1994

[NPM94] S. Nguyen, D. Pretolani and L. Markenzon "On some path problems on oriented hypergraphs", TR n.967 C.R.T, Université de Montréal, 1994 (to appear on RAIRO - Informatique Theorique et Applications)

[GLNP93] G. Gallo, G. Longo, S. Nguyen and S. Pallottino "Directed hypergraphs and applications", Discrete Applied Mathematics, 42 p. 177-201, 1993

[PS93] S. Pallottino, G. Storchi "Sull'efficienza sperimentale di algoritmi auction per la determinazione dell'albero dei cammini minimi", Ricerca Operativa, 66 p. 35-63, 1993

[GS93] G. Gallo, M.G. Scutellà "Toward a programming environment for combinatorial optimization: a case study oriented to max-flow computations", ORSA Journal on Computing, 5 p. 120-133, 1993

[CGS92] R. Cambini, G. Gallo and M.G. Scutellà "Minimum cost flows on Hypergraphs", TR 1/92, Dip. di Informatica, Univ. di Pisa, 1992

[GP92] G. Gallo, S. Pallottino "Hypergraph models and algorithms for the assembly problem", TR 6/92 Dip. di Informatica, Univ. di Pisa, 1992

[MPS91] G. Mazzoni, S. Pallottino and M.G. Scutellà "The maximum flow problem: a max-preflow approach", European Journal of Operational Research, 53 p. 257-278, 1991

[PS91] S. Pallottino and M.G. Scutellà "Strongly polynomial auction algorithms for shortest paths", Ricerca Operativa, 60, p. 33-53, 1991

[S90a] M.G. Scutellà "A note on Cherkasky's algorithm for the maximum flow problem" Ricerca Operativa 53, p. 65-75, 1990

[S90b] M.G. Scutellà "A unified algorithmic framework for Max-Flow computations (Toward the design of a combinatorial optimization programming environment)" Ph.D. Dissertation TD 1/90, Dip. di Informatica, Univ. di Pisa, 1990

[GLNP89] G. Gallo, G. Longo, S. Nguyen and S. Pallottino; Gli ipergrafi orientati: un nuovo approccio per la formulazione e risoluzione di problemi combinatori Atti delle Giornate AIRO '89, p. 217-236, 1989.

[GP88] G. Gallo and S. Pallottino "Shortest path algorithms" Annals of Operations Research 13, p.3-79,1988.

[GP86] G. Gallo e S. Pallottino "Shortest path methods: a unifying approach" Mathematical Programming Study 26, p.38-64, 1986

[SS88] M.G. Scutellà, G. Scevola "A modification of Lipski-Preparata's algorithm for the maximum matching problem on bipartite convex graphs" Ricerca Operativa 46, p. 63-77, 1988