logo sapienza

Home page of Paolo Giulio Franciosa

Valid HTML 4.0 Transitional Valid CSS!

Personal data

portrait
2000-today
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 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

Submitted

  1. N. Apollonio and P. G. Franciosa.
    On computing the Galois lattice of Bipartite Distance Hereditary graphs
    Submitted to international journal. http://arxiv.org/abs/1510.06883
  2. N. Apollonio, M. Caramia, P. G. Franciosa, and J. F. Mascari.
    A tight relation between series-parallel graphs and Bipartite Distance Hereditary graphs
    Submitted to international journal. http://arxiv.org/abs/1511.03100

International Journals

  1. 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.
  2. N. Apollonio M. Caramia, and P. G. Franciosa.
    On the Galois Lattice of Bipartite Distance Hereditary Graphs.
    Discrete Applied Mathematics, 190-91:13-23, 2015.
  3. N. Apollonio and P. G. Franciosa.
    A Characterization of Partial Directed Line Graphs
    Discrete Mathematics, 307(21):2598-2614, 2007.
  4. 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
  5. 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
  6. G. Ausiello, P. G. Franciosa, and D. Frigioni.
    Partially Dynamic Maintenance of Minimum Weight Hyperpaths.
    J. of Discrete Algorithms, 3(1):27-46, 2005.
  7. 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
  8. 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.
  9. 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
  10. 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
  11. 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.
  12. G. Brightwell and P. G. Franciosa.
    On the boolean dimension of spherical orders.
    Order, 13:233-243, 1996.
  13. 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.
  14. F. d'Amore and P. G. Franciosa.
    Separating sets of hyperrectangles.
    Internat. J. Comput. Geom. Appl., 3(2):155-165, 1993.
  15. P. G. Franciosa, D. Frigioni, and R. Giaccio.
    Semi-dynamic breadth-first search in digraphs.
    Theoret. Comput. Sci., 250:202-217, 2001.
  16. 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.
  17. 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.
  18. P. G. Franciosa and M. Talamo.
    ESPRIT project EP6881 AMUSING.
    IEEE Bulletin on Data Engineering, 16(3):46-50, 1993.

page top

International Conferences

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  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, 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.

page top

Italian Conferences

  1. 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.
  2. 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.

Incarichi Accademici

page top

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

page top