24 citations · 48 across the 15 of their papers we have counts for
16 papers
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi +2
A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with i…
Giant Components in Random Temporal Graphs
Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi +4
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi…
Planning with Biological Neurons and Synapses
Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi +2
We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that…
On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
We consider the problem of assigning appearing times to the edges of a digraph in order to maximize the (average) temporal reachability between pairs of nodes. Motivated by the app…
Public Communication can Facilitate Low-Risk Coordination under Surveillance
Amos Korman, Pierluigi Crescenzi
Consider a sub-population of rebels that wish to initiate a revolution. In order to avoid initializing a failed revolution, rebels would first strive to estimate their relative "po…
On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
A weighted point-availability time-dependent network is a list of temporal edges, where each temporal edge has an appearing time value, a travel time value, and a cost value. In th…
Simple and Fast Distributed Computation of Betweenness Centrality
Pierluigi Crescenzi, Pierre Fraigniaud, Ami Paz
Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, r…
Trade-offs in Distributed Interactive Proofs
Pierluigi Crescenzi, Pierre Fraigniaud, Ami Paz
The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of seque…
Computing top-k Closeness Centrality Faster in Unweighted Graphs
Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi +2
Given a connected graph , the closeness centrality of a vertex is defined as . This measure is widely used in the analysis of real-w…
Sigil3D: A Crowdsourcing Platform for Interactive 3D Content
Andrea Barillari, Daniele Bernardini, Pierluigi Crescenzi
In this paper we propose applying the crowdsourcing approach to a software platform that uses a modern and state-of-the-art 3D game engine. This platform could facilitate the gener…
Improving the betweenness centrality of a node by adding links
Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo +3
Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high between…
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is n…
Fast and Simple Computation of Top-k Closeness Centralities
Michele Borassi, Pierluigi Crescenzi, Andrea Marino
Closeness is an important centrality measure widely used in the analysis of real-world complex networks. In particular, the problem of selecting the k most central nodes with respe…
Into the Square - On the Complexity of Quadratic-Time Solvable Problems
Michele Borassi, Pierluigi Crescenzi, Michel Habib
This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $…
Synchronous Context-Free Grammars and Optimal Linear Parsing Strategies
Pierluigi Crescenzi, Daniel Gildea, Andrea Marino +2
Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata, are unlike context-free grammars in that they do not have a binary normal form. In ge…
Rumor Spreading in Random Evolving Graphs
Andrea Clementi, Pierluigi Crescenzi, Carola Doerr +5
Randomized gossip is one of the most popular way of disseminating information in large scale networks. This method is appreciated for its simplicity, robustness, and efficiency. In…