9 citations · 31 across the 11 of their papers we have counts for
14 papers
On Computing Large Temporal (Unilateral) Connected Components
Isnard Lopes Costa, Raul Lopes, Andrea Marino +1
A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, . Paths are sequences of adjacent edges whose appearing times are ei…
Menger's Theorem for Temporal Paths (Not Walks)
Allen Ibiapina, Raul Lopes, Andrea Marino +1
A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its (discretized) lifetime . In this setting, we ask that walks respect…
Königsberg Sightseeing: Eulerian Walks in Temporal Graphs
Andrea Marino, Ana Silva
An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph at least (resp. exactly) once. This notion was first discussed by Leonhard Euler…
Efficient Estimation of Graph Trussness
Alessio Conte, Roberto Grossi, Andrea Marino +1
A -truss is an edge-induced subgraph such that each of its edges belongs to at least triangles of . This notion has been introduced around ten years ago in social n…
Edge-Disjoint Branchings in Temporal Graphs
Victor Campos, Raul Lopes, Andrea Marino +1
A temporal digraph is a triple where is a digraph, is a function on that tells us the timestamps when a vertex is active, and is a functio…
Proximity Search For Maximal Subgraph Enumeration
Alessio Conte, Andrea Marino, Roberto Grossi +2
This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems th…
Listing Maximal Subgraphs in Strongly Accessible Set Systems
Alessio Conte, Roberto Grossi, Andrea Marino +1
Algorithms for listing the subgraphs satisfying a given property (e.g.,being a clique, a cut, a cycle, etc.) fall within the general framework of set systems. A set system (U, F) u…
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…
BUbiNG: Massive Crawling for the Masses
Paolo Boldi, Andrea Marino, Massimo Santini +1
Although web crawlers have been around for twenty years by now, there is virtually no freely available, opensource crawling software that guarantees high throughput, overcomes the…
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…
Enumerating Cyclic Orientations of a Graph
Alessio Conte, Roberto Grossi, Andrea Marino +1
Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obta…
Entity-Linking via Graph-Distance Minimization
Roi Blanco, Paolo Boldi, Andrea Marino
Entity-linking is a natural-language-processing task that consists in identifying the entities mentioned in a piece of text, linking each to an appropriate item in some knowledge b…
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…
Optimal Listing of Cycles and st-Paths in Undirected Graphs
Rui Ferreira, Roberto Grossi, Andrea Marino +3
We present the first optimal algorithm for the classical problem of listing all the cycles in an undirected graph. We exploit their properties so that the total cost is the time ta…