Guido
Proietti
Selected Publications
Book Chapters
L. Forlizzi and G. Proietti
chapter 7 in E questo tutti chiamano Informatica
Sapienza Università Editrice, 2015.
2. Access Methods and Query Processing Techniques
A. Di Pasquale, L. Forlizzi, C.S. Jensen, Y. Manolopoulos, E. Nardelli, D. Pfoser, G. Proietti, S. Saltenis, Y. Theodoridis, T. Tzouramanis, and M. Vassilakopoulos
chapter 6 in Spatio-Temporal
Databases: The CHOROCHRONOS Approach
Lecture Notes in Computer Science Vol. 2520, Springer-Verlag, 2003.
Journals
1. New Approximation Algorithms for the Heterogeneous Weighted Delivery Problem D. Biḷ, L. Gualà, S. Leucci, G. Proietti, and M. Rossi Theoretical Computer Science, 932: 102-115 (2022). (A preliminary version of this paper got the best student paper award at the 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO’21), June 28 - July 1, Wrocław, Poland, 167-184, 2021.)
2. Cutting Bamboo Down to Size D. Biḷ, L. Gualà, S. Leucci, G. Proietti, and G. Scornavacca Theoretical Computer Science, 909: 54-67 (2022). (A preliminary version of this paper got the best paper award at the 10th International Conference on Fun with Algorithms (FUN'20), May 30-June 3, 2022, Favignana, Italy. Vol. 157 of LIPIcs Series, Schloss Dagstuhl, 5:1-5:18, 2020.)
3. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees D. Biḷ, L. Gualà, S. Leucci, and G. Proietti Algorithmica, 84(1), 37-59 (2022). (A preliminary version of this paper was presented at the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS’16), February 17-20, 2016, Orléans, France. Vol. 47 of LIPIcs Series, Schloss Dagstuhl, 18:1-18:14, 2016.)
4. Network Creation Games with Traceroute-Based Strategies D. Biḷ, L. Gualà, S. Leucci, and G. Proietti Algorithms 14(2): 35 (2021) (A preliminary version of this paper was presented at the 21th International Colloquium on Structural Information and Communication Complexity (SIROCCO’14), July 23-25, 2014, Hida Takayama, Japan. Vol. 8576 of Lecture Notes in Computer Science, Springer, 210-223, 2014.)
5. Hardness of an Asymmetric 2-Player Stackelberg Network Pricing Game D. Biḷ, L. Gualà, and G. Proietti, Algorithms, 14(1):8 (2021).
6. Tracking Routes in Communication Networks D. Biḷ, L. Gualà, S. Leucci, and G. Proietti Theoretical Computer Science, 844:1-15 (2020). (A preliminary version of this paper was presented at the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO’19), 1-4 July 2019, L’Aquila, Italy. Vol. 11639 of Lecture Notes in Computer Science, Springer, 81-93, 2019.)
7. An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner D. Biḷ, F. Colella, L. Gualà, S. Leucci, and G. Proietti Algorithmica, 82(2), 279-299 (2020). (Special Journal Issue on selected papers from the 28th International Symposium on Algorithms and Computation (ISAAC’17) 9-12 December 2017, Phuket, Thailand. Vol. 92 of LIPIcs Series, Schloss Dagstuhl, 14:1-14:13, 2017.)
8. Hardness, Approximability, and Fixed-parameter Tractability of the Clustered Shortest-path Tree Problem M. D’Emidio, L. Forlizzi, D. Frigioni, S. Leucci, and G. Proietti Journal of Combinatorial Optimization, 38(1):165-184 (2019).
9. Fault-Tolerant Approximate Shortest-Path Trees D. Biḷ, L. Gualà, S. Leucci, and G. Proietti Algorithmica, 80:3437-3460 (2018). (A preliminary version of this paper was presented at the 22nd European Symposium on Algorithms (ESA’14), September 8-10, 2014, Wroclaw, Poland. Vol. 8737 of Lecture Notes in Computer Science, Springer, 137-148, 2014.)
10. Exact and Approximate Algorithms for Movement Problems on (Special Classes of) Graphs D. Biḷ, L. Gualà, S. Leucci, and G. Proietti Theoretical Computer Science, 652:86–101 (2016). (A preliminary version of this paper was presented at the 20th Colloquium on Structural Information and Communication Complexity (SIROCCO'13), July 1-3, 2013, Ischia, Italy. Vol. 8179 of Lecture Notes in Computer Science, Springer, 322-333, 2013.)
11. Locality-Based Network Creation Games D. Biḷ, L. Gualà, S. Leucci, and G. Proietti ACM Transactions on Parallel Computing, 3(1), Article 6, (2016). (Special Journal Issue on selected papers from the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'14), June 23-25, 2014, Prague, Czech Republic. ACM Press, 277-286.)
12. Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates: New Algorithms and Experiments A. D’Andrea, M. D’Emidio, D. Frigioni, S. Leucci, and G. Proietti ACM Journal on Experimental Algorithmics, 20(1), Article 5, (2015).
13. A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree D. Biḷ, L. Gualà, and G. Proietti Algorithmica, 73(3):547-570 (2015). (Special Journal Issue on selected papers from the 21st European Symposium on Algorithms (ESA'13), September 2-4, 2013, Sophia Antipolis, France. Vol. 8125 of Lecture Notes in Computer Science, Springer, 157-168.)
14. Bounded-Distance Network Creation Games D. Biḷ, L. Gualà, and G. Proietti ACM Transactions on Economics and Computation, 3(3), Article 16, (2015). (A preliminary version of this paper was presented at the 8th International Workshop on Internet & Network Economics (WINE'12), December 9-12, 2012, Liverpool, UK. Vol. 7695 of Lecture Notes in Computer Science, Springer, 72–85.)
15. The Max-Distance Network Creation Game on General Host Graphs D. Biḷ, L. Gualà, S. Leucci, and G. Proietti Theoretical Computer Science, 573:43-53 (2015). (A preliminary version of this paper was presented at the 8th International Workshop on Internet & Network Economics (WINE'12), December 9-12, 2012, Liverpool, UK. Vol. 7695 of Lecture Notes in Computer Science, Springer, 393–406.)
16. Specializations and Generalizations of the Stackelberg Minimum Spanning Tree Game D. Biḷ, L.
Gualà, S. Leucci, and G. Proietti (A preliminary version of this paper was presented at the 6th International Workshop on Internet & Network Economics (WINE'10), December 13-17, 2010, Stanford, California, USA. Vol. 6484 of Lecture Notes in Computer Science, Springer, 75-86.)
17. Network Verification via Routing Table Queries E. Bampas, D. Biḷ, G. Drovandi, L. Gualà, R. Klasing, and G. Proietti Journal of Computer and System Sciences, 81(1):234-248 (2015). (A preliminary version of this paper was
presented at the 18th Colloquium on Structural
Information and Communication Complexity (SIROCCO'11), June 26-29, 2011, Gdansk, Polonia.
18. Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree D. Biḷ, L. Gualà, and G. Proietti Algorithmica, 68(2):337-357 (2014). (A preliminary version of this paper was presented at the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS’10), August 23-27, 2010, Brno, Czech Republic. Vol. 6281 of Lecture Notes in Computer Science, Springer, 138-149.)
19. Improved Approximability and Non-approximability Results for Graph Diameter Decreasing Problems D. Biḷ, L.
Gualà, and G. Proietti (Special Journal Issue on selected papers from the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS’10), August 23-27, 2010, Brno, Czech Republic. Vol. 6281 of Lecture Notes in Computer Science, Springer, 150-161.)
20. Approximating the Metric TSP in Linear
Time (A preliminary version of this paper was
presented at the 34th Int. Workshop on
Graph-Theoretic Concepts in Computer Science (WG'08), 30 June-2 July, 2008, Durham University, UK. Vol. 5344 of Lecture Notes in Computer Science, Springer, 43-54.) 21. Approximate Mechanisms for the Metric TSP
and other Graph Traversal Problems (Special Journal Issue on selected papers from the 3rd International Workshop on Internet & Network Economics (WINE'07), December 12-14, 2007, San Diego, USA. Vol. 4858 of Lecture Notes in Computer Science, Springer, 503-514.)
22. Dynamic Mechanism Design 23.
Strongly
Polynomial-Time Truthful Mechanisms in One Shot 24.
On
k-Connectivity Problems with Sharpened Triangle Inequality 25.
On the
Complexity of Minimizing Interference in Ad-Hoc and Sensor Networks 26.
Exact and
Approximate Truthful Mechanisms for the Shortest-Paths Tree Problem 27.
On the
Approximability of TSP on Local Modifications of Optimally Solved Instances 28.
Swapping a
Failing Edge of a Shortest Paths Tree by Minimizing the Average Stretch
Factor 29.
Efficient
Truthful Mechanisms for the Single-source Shortest Paths Tree Problem 30.
Efficient
Management of Transient Station Failures in Linear Radio Communication
Networks with Bases
31.
On the
Stability of Approximation for Hamiltonian Path Problems 32.
Efficient
Unbalanced Merge-Sort
33.
On the Hardness
of Constructing Minimal Biconnected Spanning Subgraphs in Complete Graphs
with Sharpened Triangle Inequality 34.
Nearly Linear
Time Minimum Spanning Tree Maintenance for Transient Node Failures 35.
Polynomial Time
Algorithms for 2-Edge-Connectivity Augmentation Problems 36.
Swapping a
Failing Edge of a Single Source Shortest Paths Tree is Good and Fast 37.
Finding the
Most Vital Node of a Shortest Path 38.
Finding All the
Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures 39. Efficient ATM Layouts with Bounded Hop
Count and Congestion
40. A Faster Computation of the Most Vital Edge of a Shortest Path 41. Accurate Modeling of Region Data 42. A Generalized Comparison of Linear Representations of Thematic
Layers 43. An Efficient Spatial Access Method for Spatial Images Containing
Multiple Non-Overlapping Features 44. Analysis of Range Queries and Self Spatial Join Queries on Real
Region Datasets Stored Using an R-tree 45. An Optimal Algorithm for Decomposing a Window into its Maximal
Quadtree Blocks 46. Probabilistic Models for Images and Quadtrees: Differences and
Equivalences 47. Intersection Reporting on Two Collection of Disjoint Sets 48. Finding the Detour-Critical Edge of a Shortest Path between Two
Nodes 49. MOF-tree: a Spatial Access Method to Manipulate Multiple
Overlapping Features 50. Time and Space Efficient Secondary Memory Representation of
Quadtrees 51. The MOF+-tree: a Space Efficient Representation of Images
Containing Multiple Overlapping Features 52. On the Creation of Quadtrees by Using a Branching Process 53. Efficient Secondary Memory Processing of Window Queries on Spatial
Data
54. An Optimal Resolution Sensitive Pyramid Representation for
Hierarchical Memory Models |
Conferences
1. Temporal Queries for Dynamic Temporal Forests. D. Biḷ, L. Gualà, S. Leucci, G. Proietti, and A. Straziota 35th International Symposium on Algorithms and Computation, (ISAAC’24), December 8-11, 2024, Sydney, Australia. Vol. 322 of LIPIcs Series, Schloss Dagstuhl, 11:1-11:16, 2024.
2. Optimizing Nozzle Travel Time in Proton Therapy M. Spezialetti, R. Di Filippo, R. Gimenez De Lorenzo, G.L. Gravina, G. Placidi, G. Proietti, F. Rossi, S. Smriglio, J.M.R.S. Tavares, F. Vittorini, and F. Mignosi 35th IEEE International Symposium on Computer-Based Medical Systems (CBMS’22), July 21-23, 2022, Shenzen, China. IEEE Computer Society, 441-446, 2022.
3. Single-source Shortest p-disjoint Paths: Fast Computation and Sparse Preservers D. Biḷ, G. D'Angelo, L. Gualà, S. Leucci, G. Proietti, and M. Rossi 39th International Symposium on Theoretical Aspects of Computer Science (STACS’22), March 15-18, 2022, Marseille, France. Vol. 219 of LIPIcs Series, Schloss Dagstuhl, 12:1-12:21, 2022.
4. Dual-mode Greedy Algorithms Can Save Energy B. Geissmann, S. Leucci, C.-H. Liu, P. Penna and G. Proietti 30th International Symposium on Algorithms and Computation (ISAAC'19), December 8-11, 2019, Shanghai, China. Vol. 149 of LIPIcs Series, Schloss Dagstuhl, 64:1-64:18, 2019.
5. On the PSPACE-completeness of Peg Duotaire and other Peg-jumping Games D. Biḷ, L. Gualà, S. Leucci, G. Proietti, and M. Rossi 9th International Conference on Fun with Algorithms (FUN'18), June 13-15, 2018, La Maddalena, Italy. Vol. 100 of LIPIcs Series, Schloss Dagstuhl, 8:1-8:15, 2018.
6. Efficient Oracles and Routing Schemes for Replacement Paths D. Biḷ, K. Choudhary, L. Gualà, S. Leucci, M. Parter, and G. Proietti 35th International Symposium on Theoretical Aspects of Computer Science (STACS’18), February 28-March 3, 2018, Caen, France. Vol. 96 of LIPIcs Series, Schloss Dagstuhl, 13:1-13:15, 2018.
7. Simple and Practically Efficient Fault-Tolerant 2-Hop Cover Labelings F. Colella, M. D'Emidio, and G. Proietti 18th Italian Conference on Theoretical Computer Science (ICTCS’17) 26-29 September 2017, Naples, Italy. CEUR Workshop Proceedings 1949, 51-62, 2017.
8. Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges D. Biḷ, F. Colella, L. Gualà, S. Leucci, and G. Proietti 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO’17), 19-22 June 2017, Porquerolles, France Vol. 10641 of Lecture Notes in Computer Science, Springer, 303-317, 2017.
9. Rational Fair Consensus in the GOSSIP Model A. Clementi, L. Gualà, G. Proietti, and G. Scornavacca 31st IEEE International Parallel & Distributed Processing Symposium (IPDPS’17), May 29-June 2, 2017, Orlando, Florida, USA. IEEE Computer Society, 163-171, 2017.
10. On the Clustered Shortest-Path Tree Problem (Short Communication) M. D’Emidio, L. Forlizzi, D. Frigioni, S. Leucci, and G. Proietti 17th Italian Conference on Theoretical Computer Science (ICTCS'16), September 7-9, 2016, Lecce, Italy. Vol. 1720 of CEUR Workshop Proceedings, 263--268, 2016.
11. Compact and Fast Sensitivity Oracles for Single-Source Distances D. Biḷ, L. Gualà, S. Leucci, and G. Proietti 24th European Symposium on Algorithms (ESA’16), August 22-24, 2016, Aarhus, Denmark. Vol. 57 of LIPIcs Series, Schloss Dagstuhl, 13:1-13:14, 2016.
12. Sequence Hypergraphs K. Bohmova, J. Chalopin, M. Mihalák, G. Proietti and P. Widmayer 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG’16), June 22-24, 2016, İstanbul, Turkey. Vol. 9941 of Lecture Notes in Computer Science, Springer, 1-13, 2016.
13. Path-Fault-Tolerant Approximate Shortest-Path Trees A. D’Andrea, M. D’Emidio, D. Frigioni, S. Leucci, and G. Proietti 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO’15), July 15-17, 2015, Mont Serrat, Spain. Vol. 9439 of Lecture Notes in Computer Science, Springer, 224-238, 2015.
14. A Faster Computation of All the Best Swap Edges of a Tree Spanner D. Biḷ, F. Colella, L. Gualà, S. Leucci, and G. Proietti 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO’15), July 15-17, 2015, Mont Serrat, Spain. Vol. 9439 of Lecture Notes in Computer Science, Springer, 239-253, 2015.
15. Improved Purely Additive Fault-Tolerant Spanners D. Biḷ, F. Grandoni, L. Gualà, S. Leucci, and G. Proietti 23rd European Symposium on Algorithms (ESA’15), September 14-16, 2015, Patras, Greece. Vol. 9294 of Lecture Notes in Computer Science, Springer, 167-178, 2015.
16. Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches A. D’Andrea, M. D’Emidio, D. Frigioni, S. Leucci, and G. Proietti 13th International Symposium on Experimental Algorithms (SEA'14), June 29-July 1, 2014, Copenhagen, Denmark. Vol. 8504 of Lecture Notes in Computer Science, Springer, 283-294, 2014.
17. Polygon-Constrained Motion Planning Problems D. Biḷ, Y. Disser, L. Gualà, M. Mihal’ak, G. Proietti, and P. Widmayer, 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS'13), September 5-6, 2013, Sophia Antipolis, France. Vol. 8243 of Lecture Notes in Computer Science, Springer, 67-82, 2013.
18. Dynamically Maintaining Shortest Path Trees Under Batches of Updates A. D’Andrea, M. D’Emidio, D. Frigioni, S. Leucci, and G. Proietti 20th Colloquium on Structural Information and Communication Complexity (SIROCCO'13), July 1-3, 2013, Ischia, Italy. Vol. 8179 of Lecture Notes in Computer Science, Springer, 286-297, 2013.
19. Reoptimizing the Strengthened Metric TSP on Multiple Edge Weight Modifications A. D'Andrea
and G. Proietti Vol. 7276 of Lecture Notes in Computer Science, Springer, 111-122.
20. Stability of Networks in Stretchable Graphs D. Biḷ, M.
Gatto, L. Gualà, G. Proietti, and P. Widmayer
21. Computational Aspects of a 2-player
Stackelberg Shortest Paths Tree Game 22. Locating Facilities on a Network to Minimize their Average Service
Radius 23. An Algorithm Composition Scheme Preserving Monotonicity 24. Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph
Radii 25. Reusing Optimal TSP Solutions for Locally Modified Input Instances 26. Hardness of Designing a Truthful Mechanism for a Spanning
Arborescence Bicriteria Problem 27. On the Existence of Truthful Mechanisms for the Minimum-cost
Approximate Shortest-paths Tree Problem 28. A Truthful Mechanism for the Non-utilitarian Minimum Radius
Spanning Tree Problem 29. A Truthful (2-2/k)-Approximation Mechanism
for the Steiner Tree Problem with k Terminals 30. Range Augmentation Problems in Static Ad-hoc Wireless Networks 31. Augmenting the Edge-connectivity of a Spider Tree 32. A 5/4-approximation Algorithm for Biconnecting a Graph with a
Given Hamiltonian Path 33. Truthful
Mechanisms for Building Trust in E-commerce 34. A Lower Bound for the DRT* with Complete Correction Technique 35. Edge-connectivity Augmentation and Network Matrices 36. Truthful
Mechanisms for Generalized Utilitarian Problems 37.
An RP*
Extension with Almost Constant Amortized Costs 38.
Optimal MST
Maintenance for Transient Deletion of Every Node in Planar Graphs 39.
Quality of
Service in Wireless Networks 40.
A Faster
Approximation Algorithm for 2-Edge-Connectivity Augmentation 41.
An Improved
Upper Bound for Scalable Distributed Search Trees 42.
Polynomial Time
Algorithms for Edge-Connectivity Augmentation of Hamiltonian Paths 43.
Dynamic
Maintenance Versus Swapping: an Experimental Study on Shortest Paths Trees, 44.
Maintaning a
Minimum Spanning Tree Under Transient Node Failures 45.
Size Estimation
of the Intersection Join Between Two Line Segment Datasets 46.
S*-tree: an
Improved S+-tree for Coloured Images 47.
A Roboust Image
Mosaicing Technique Capable of Creating Integrated Panoramas 48.
How to Swap a
Failing Edge of a Single Source Shortest Paths Tree 49.
I/O Complexity
for Range Queries on Region Data Stored Using an R-tree 50.
Selectivity
Estimation of Spatial Queries for Line Segment Datasets 51.
Image Indexing
and Retrieval Based on Human Perceptual Color Clustering 52.
Efficient
Inserting of Approximately Sorted Sequences of Elements into a Dictionary 53.
Efficient ATM
Layouts with Bounded Hop Count and Congestion 54.
An Output
Sensitive Solution to the Set Union and Intersection Problem 55.
QR-tree: a
Hybrid Spatial Data Structure 56.
On the
Generation of Aggregated Random Spatial Regions 57.
A multistage
approach to complex document interpretation 58.
Managing
overlapping features in spatial database applications 59.
An Accurate
Model for Quadtrees Representing Noiseless Images 60.
A Hybrid Pointerless
Representation of Quadtrees for Efficient Processing of Window Queries 61.
Raster to
Object Conversion Aided by Knowledge Based Image Processing |