Home page of Paolo Giulio Franciosa

Personal data

2010-today

Full Professor in Computer Science at the Statistics school of Sapienza University of Rome

2000-2010

Associate Professor in Computer Science at the Statistics school of Sapienza University of Rome

1994-2000

Researcher in Computer Science at the Statistics school of Sapienza University of Rome

1994

Ph.D. in Computer Science at the department of Computer and system sciences of Sapienza University of Rome.

1988

Degree in Electronic Engineering, 110/110 cum laude, at Sapienza University of Rome

Born in 1963

Research interests

page top

Multidimensional data structures and partial orders

Geometry of rectangles

Dynamic graph algorithms

Graph spanners

Combinatorial aspects of graphs

Is member of the research center Cyber Intelligence and Information Security (CIS)

Participates in Cyber Security National Lab

Selected publications

page top

A list of publications is available in several bibliography repositories, such as DBLP (search "Franciosa") or MathSciNet

International Journals

1. L. Balzotti, P. G. Franciosa
   How vulnerable is an undirected planar graph with respect to max flow
   Networks (2024), 1-17. 10.1002/net.22205
2. N. Apollonio, P. G. Franciosa, and D. Santoni.
   Network homophily via tail inequalities
   PHYSICAL REVIEW. E. (2023), - ISSN 2470-0045. - 108:5 10.1103/PhysRevE.108.054130
3. N. Apollonio, D. Blankenberg, F. Cumbo, P. G. Franciosa, and D. Santoni
   Evaluating homophily in networks via HONTO (HOmophily Network TOol): a case study of chromosomal interactions in human PPI networks
   Bioinformatics, Vol. 39, No. 1, (2023), 10.1093/bioinformatics/btac763
4. L. Balzotti, P. G. Franciosa
   Non-crossing shortest paths lengths in planar graphs in linear time.
   Discrete Applied Mathematics, 346, (2023) 10.1016/j.dam.2023.12.011.
5. E. Boros, P. G. Franciosa, V. Gurvich, and M. Vyalyi
   Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies.
   Int. J. Game Theory, 2023. DOI: 10.1007/s00182-023-00875-y.
6. N. Apollonio, P. G. Franciosa, and D. Santoni.
   A novel method for assessing and measuring homophily in networks through second-order statistics.
   Scientific Reports 12, 9757, 2022. https://doi.org/10.1038/s41598-022-12710-7"
7. L. Balzotti, and P. G. Franciosa.
   Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time.
   J. Graph Algorithms Appl. Vol 26 No.1 (2022) 10.7155/jgaa.00610
8. N. Apollonio, M. Caramia, P. G. Franciosa, and J. F. Mascari.
   A tight relation between series-parallel graphs and Bipartite Distance Hereditary graphs
   The Art of Discrete and Applied Mathematics Vol 5 No.1 (2021) 10.26493/2590-9770.1396.3c7
9. G. Ausiello, P. G. Franciosa, I. Lari, A. Ribichini.
   Max flow vitality in general and planar graphs.
   Networks, 74(1): 70-78, 2019
10. F. d'Amore and P. G. Franciosa.
    A low arithmetic-degree algorithm for computing proximity graphs.
    Internat. J. Comput. Geom. Appl., 28(3), 2018.
11. N. Apollonio and P. G. Franciosa.
    On computing the Galois lattice of Bipartite Distance Hereditary graphs
    Discrete Applied Mathematics, 226:1-9, 2017. DOI: http://arxiv.org/abs/1510.06883
12. G. Ausiello, P. G. Franciosa, G. F. Italiano, A. Ribichini.
    On Resilient Graph Spanners.
    Algorithmica, 74(4):1363-1385, 2016. DOI: 10.1007/s00453-015-0006-x
13. N. Apollonio, M. Caramia, and P. G. Franciosa.
    On the Galois Lattice of Bipartite Distance Hereditary Graphs.
    Discrete Applied Mathematics, 190-191:13-23, 2015.
14. G. Ausiello, P. G. Franciosa, G. F. Italiano, A. Ribichini.
    Computing graph spanners in small memory: fault-tolerance and streaming.
    Discrete Mathematics, Algorithms and Applications, 2(4):591-605, 2010. DOI: 10.1142/S1793830910000905
15. N. Apollonio and P. G. Franciosa.
    On the Complexity of Recognizing Directed Path Families.
    Discrete Applied Mathematics, 157(11):2525-2535, 2009. DOI: 10.1016/j.dam.2009.03.006
16. G. Ausiello, C. Demetrescu, P. G. Franciosa, G. F. Italiano, A. Ribichini.
    Graph Spanners in the Streaming Model: An Experimental Study.
    Algorithmica, 55(2):346-374, 2009. DOI: 10.1007/s00453-008-9216-9
17. G. Ausiello, P. G. Franciosa, G. F. Italiano.
    Small stretch (α, β)-spanners in the streaming model.
    Theoret. Comput. Sci., 410(36):3406-3413, 2009. DOI: 10.1016/j.tcs.2008.04.022
18. N. Apollonio and P. G. Franciosa.
    A Characterization of Partial Directed Line Graphs
    Discrete Mathematics, 307(21):2598-2614, 2007.
19. G. Ausiello, P. G. Franciosa, G. F. Italiano.
    Small stretch spanners on dynamic graphs.
    Journal of Graph Algorithms and Applications, 10(2):365-385, 2006.
20. G. Ausiello, P. G. Franciosa, and D. Frigioni.
    Partially Dynamic Maintenance of Minimum Weight Hyperpaths.
    J. of Discrete Algorithms, 3(1):27-46, 2005.
21. P. G. Franciosa, D. Frigioni, and R. Giaccio.
    Semi-dynamic breadth-first search in digraphs.
    Theoret. Comput. Sci., 250:202-217, 2001.
22. P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter.
    Efficient searching with linear constraints.
    J. of Comput. and System Sci., 61(2):192-216, 2000.
23. P. G. Franciosa, G. Gambosi, and U. Nanni.
    The incremental maintenance of a Depth-First-Search tree in directed acyclic graphs.
    Inform. Process. Lett., 61:113-120, 1997.
24. B. Becker, P. G. Franciosa, S. Gschwind, S. Leonardi, T. Ohler, and P. Widmayer.
    Enclosing a set of objects by two minimum area rectangles.
    J. Algorithms, 21:520-541, 1996.
25. G. Brightwell and P. G. Franciosa.
    On the boolean dimension of spherical orders.
    Order, 13:233-243, 1996.
26. P. G. Franciosa, C. Gaibisso, G. Gambosi, and M. Talamo.
    A convex hull algorithm for points with approximately known positions.
    Internat. J. Comput. Geom. Appl., 4(2):153-163, 1994.
27. F. d'Amore and P. G. Franciosa.
    Separating sets of hyperrectangles.
    Internat. J. Comput. Geom. Appl., 3(2):155-165, 1993.
28. P. G. Franciosa and M. Talamo.
    ESPRIT project EP6881 AMUSING.
    IEEE Bulletin on Data Engineering, 16(3):46-50, 1993.
29. F. d'Amore and P. G. Franciosa.
    On the optimal binary plane partition for sets of isothetic rectangles.
    Inform. Process. Lett., 44:255-259, 1992.

page top

International Conferences

1. L. Balzotti, P. G. Franciosa.
   Non-crossing Shortest Paths Lengths in Planar Graphs in Linear Time.
   Proceedings of Algorithms and Complexity - 13th International Conference, CIAC 2023 (2023), 67-81, doi 10.1007/978-3-031-30448-4_6
2. L. Balzotti, P. G. Franciosa.
   How Vulnerable is an Undirected Planar Graph with Respect to Max Flow.
   Proceedings of Algorithms and Complexity - 13th International Conference, CIAC 2023 (2023), 82-96, doi 10.1007/978-3-031-30448-4_7
3. L. Balzotti, P. G. Franciosa.
   Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time.
   Proceedings of the 17th International Computer Science Symposium in Russia (2022), 77-95
4. N. Apollonio, M. Caramia, and P. G. Franciosa.
   On the Galois Lattice of Bipartite Distance Hereditary Graphs.
   In 25th International Workshop on Combinatorial Algorithms (IWOCA 2014), volume 8986 of Lecture Notes in Computer Science. Springer-Verlag, 2015.
5. G. Ausiello, P. G. Franciosa, G. F. Italiano, A. Ribichini.
   On Resilient Graph Spanners.
   In Algorithms - ESA 2013 - 21st Annual European Symposium,
   volume 8125 of Lecture Notes in Computer Science, pages 85-96. Springer-Verlag, 2013.
   http://arxiv.org/abs/1303.1559
6. G. Ausiello, P. G. Franciosa, G. F. Italiano, A. Ribichini.
   Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming
   In Proc. of Computing and Combinatorics, 16th Annual International Conference (COCOON 2010), volume 6169 of Lecture Notes in Computer Science, pages 160-172. Springer-Verlag, 2010.
7. G. Ausiello, C. Demetrescu, P. G. Franciosa, G. F. Italiano, A. Ribichini.
   Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments.
   In 15th Annual European Symposium on Algorithms (ESA '07), volume 4698 of Lecture Notes in Computer Science, pages 605-617. Springer-Verlag, 2007.
8. G. Ausiello, P. G. Franciosa, G. F. Italiano.
   Small stretch spanners on dynamic graphs.
   In 13th Annual European Symposium on Algorithms (ESA '05), volume 3669 of Lecture Notes in Computer Science, pages 532-543. Springer-Verlag, 2005.
9. G. Ausiello, P. G. Franciosa, D. Frigioni.
   Directed Hypergraphs: Problems, Algorithmic Results and a Novel Decremental Approach.
   In Proc. 7th Italian Conf. on Theoret. Computer Science (ICTCS2001), volume 2202 of Lecture Notes in Computer Science, pages 312-327. Springer, 2001.
10. P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter.
    Efficient searching with linear constraints.
    In Proc. Annu. ACM Sympos. Principles Database Syst., pages 169-178, 1998.
11. F. d'Amore, P. G. Franciosa, and G. Liotta.
    Robust computation of Euclidean minimum spanning trees.
    In Abstracts 14th European Workshop Comput. Geom., pages 29-31, 1998.
12. F. d'Amore, P. G. Franciosa, and G. Liotta.
    A robust region approach to the computation of geometric graphs.
    In Algorithms -- Proc. 4th Annu. European Sympos. Algorithms, volume 1461 of Lecture Notes in Computer Science, pages 320-333. Springer-Verlag, 1998.
13. G. Ausiello, P. G. Franciosa, D. Frigioni, and R. Giaccio.
    Decremental maintenance of reachability in hypergraphs and minimum models of Horn formulae.
    In Proc. 8th Annu. Internat. Sympos. Algorithms Comput., volume 1350 of Lecture Notes in Computer Science, pages 122-131. Springer, 1997.
14. F. d'Amore, P. G. Franciosa, R. Giaccio, and M. Talamo.
    Maintaining maxima under boundary updates.
    In Proc. 3rd Italian Conf. on Algorithms and Complexity, volume 1203 of Lecture Notes in Computer Science, pages 100-109. Springer, 1997.
15. P. G. Franciosa, D. Frigioni, and R. Giaccio.
    Semi-dynamic shortest paths and breadth-first search in digraphs.
    In Proc. 14th Sympos. Theoret. Aspects Comput. Sci., volume 1200 of Lecture Notes in Computer Science, pages 33-46. Springer, 1997.
16. P. G. Franciosa.
    A note on the boolean dimension of spherical orders.
    In Workshop on Combinatorics, also as Technical Report 95-309, Charles University, Prague (CZ), 1995.
17. P. G. Franciosa, G. Gambosi, and U. Nanni.
    On the structure of DFS-forests on directed graphs and the dynamic maintenance of DFS on DAG's.
    In 2nd Annual European Symposium on Algorithms (ESA '94), volume 855 of Lecture Notes in Computer Science, pages 343-353. Springer-Verlag, 1994.
18. P. G. Franciosa and M. Talamo.
    Orders, k-sets and fast halfplane search on paged memory.
    In Proc. Workshop on Orders, Algorithms and Applications, volume 831 of Lecture Notes in Computer Science, pages 117-127. Springer-Verlag, 1994.
19. B. Becker, P. G. Franciosa, S. Gschwind, T. Ohler, G. Thiemt, and P. Widmayer.
    Enclosing many boxes by an optimal pair of boxes.
    In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lecture Notes in Computer Science, pages 475-486. Springer-Verlag, 1992.
20. F. d'Amore and P. G. Franciosa.
    On the optimal binary plane partition for sets of isothetic rectangles.
    In Proc. 4th Canad. Conf. Comput. Geom., pages 1-5, 1992.
21. B. Becker, P. G. Franciosa, S. Gschwind, T. Ohler, G. Thiemt, and P. Widmayer.
    An optimal algorithm for approximating a set of rectangles by two minimum area rectangles.
    In Proc. Computational Geometry: Methods, Algorithms and Applications, volume 553 of Lecture Notes in Computer Science, pages 13-25. Springer-Verlag, 1991.
22. P. G. Franciosa, C. Gaibisso, and M. Talamo.
    An on-line convex hull algorithm on reals.
    In Proc. Internat. Conf. Young Comp. Scientists, pages 293-299, 1991.
23. P. G. Franciosa and E. Nardelli.
    A guaranteed approximation algorithm for on-line computing quad-tree border.
    In Proc. Internat. Workshop on DBMSs for Geographical Applications, pages 245-257. Springer-Verlag, 1991.
24. F. d'Amore and P. G. Franciosa.
    Separating sets of hyperrectangles.
    In Proc. 15th Internat. Sympos. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 165-172. Springer-Verlag, 1990.

page top

Italian Conferences

1. F. d'Amore and P. G. Franciosa.
   Fast single precision evaluation of sign of determinants.
   In Proc. of 6th Italian Conf. on Theoretical Computer Science, pages 77-89, 1998.
2. F. d'Amore and P. G. Franciosa.
   Progetto e realizzazione di un sistema per la gestione di dati geometrici basato su grid file.
   In Proc. of Congresso A.I.C.A., pages 345-362, 1989.

Incarichi Accademici

page top

• Dal 2023 è vicedirettore del Dipartimento di Scienze statistiche di Sapienza.
• Dal 2019 è membro del comitato direttivo del Centro di Ricerca Cyber Intelligence e Information Security (CIS) di Sapienza.
• Dal 2013 al 2022 è stato membro del Comitato di Monitoraggio della Facoltà di Ingegneria dell'Informazione, Informatica e Statistica.
• Dal 2008 al 2011 è stato membro del Comitato InfoSapienza, che ha compiti di proposta al Consiglio di Amministrazione delle linee di indirizzo nonché di valutazione delle attività del Centro InfoSapienza.
• Dal 2005 al 2010 è stato rappresentante eletto dei professori di seconda fascia nella Giunta Tecnico-Amministrativa dell'Ateneo federato della Scienza e della tecnologia.
• Dal 2005 al 2010 è stato rappresentante eletto dei professori di seconda fascia nella Giunta di Facoltà della facoltà di Scienze statistiche.
• Dal 2002 al 2014 ha fatto parte del Nucleo di valutazione di facoltà per la facoltà di Scienze statistiche della Sapienza. Nell'ambito di questa attività ha progettato e curato la realizzazione di un sistema per il monitoraggio della carriera e del profitto degli studenti iscritti alla facoltà.
• È stato referente di rete per il dipartimento di Scienze statistiche.
• Ha progettato e seguito la realizzazione del sistema per la valutazione della didattica via web con gli studenti della ex facoltà di Scienze Statistiche.

Contacts

page top

current address:

Sapienza University of Rome
Dipartimento di Scienze statistiche
piazzale Aldo Moro, 5
00185 Roma
Italy

email: paolo.MY_SURNAME@uniroma1.it
email: paolo.IL_MIO_COGNOME@uniroma1.it

tel: (+39)-06-49910496
fax: (+39)-06-4959241