5 citations · 15 across the 12 of their papers we have counts for
14 papers
Network homophily via tail inequalities
Nicola Apollonio, Paolo G. Franciosa, Daniele Santoni
Homophily is the principle whereby "similarity breeds connections". We give a quantitative formulation of this principle within networks. Given a network and a labeled partition of…
A Linear Time Algorithm for Computing Max-Flow Vitality in Undirected Unweighted Planar Graphs
Giorgio Ausiello, Lorenzo Balzotti, Paolo G. Franciosa +2
The vitality of an edge in a graph with respect to the maximum flow between two fixed vertices and is defined as the reduction of the maximum flow value caused by the remov…
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies
Endre Boros, Paolo Giulio Franciosa, Vladimir Gurvich +1
We prove that a deterministic n-person shortest path game has a Nash equlibrium in pure and stationary strategies if it is edge-symmetric (that is (u,v) is a move whenever (v,u) is…
How Vulnerable is an Undirected Planar Graph with respect to Max Flow
Lorenzo Balzotti, Paolo G. Franciosa
We study the problem of computing the vitality of edges and vertices with respect to the -max flow in undirected planar graphs, where the vitality of an edge/vertex is the …
A novel method for assessing and measuring homophily in networks through second-order statistics
Nicola Apollonio, Paolo Giulio Franciosa, Daniele Santoni
We present a new method for assessing and measuring homophily in networks whose nodes have categorical attributes, namely when the nodes of networks come partitioned into classes (…
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
Lorenzo Balzotti, Paolo G. Franciosa
Given a set of well-formed terminal pairs on the external face of an undirected planar graph with unit edge weights, we give a linear-time algorithm for computing the union of non-…
Computing Lengths of Non-Crossing Shortest Paths in Planar Graphs
Lorenzo Balzotti, Paolo G. Franciosa
Given a plane undirected graph with non-negative edge weights and a set of terminal pairs on the external face, it is shown in Takahashi et al. (Algorithmica, 16, 1996, pp.…
Max-flow vitality in undirected unweighted planar graphs
Giorgio Ausiello, Paolo G. Franciosa, Isabella Lari +1
We show a fast algorithm for determining the set of edges in a planar undirected unweighted graph, whose deletion reduces the maximum flow between two fixed vertices. This is a spe…
Max flow vitality in general and -planar graphs
Giorgio Ausiello, Paolo Giulio Franciosa, Isabella Lari +1
The \emph{vitality} of an arc/node of a graph with respect to the maximum flow between two fixed nodes and is defined as the reduction of the maximum flow caused by the rem…
A tight relation between series-parallel graphs and Bipartite Distance Hereditary graphs
Nicola Apollonio, Massimiliano Caramia, Paolo Giulio Franciosa +1
Bandelt and Mulder's structural characterization of Bipartite Distance Hereditary graphs asserts that such graphs can be built inductively starting from a single vertex and by repe…
On Computing the Galois Lattice of Bipartite Distance Hereditary Graphs
Nicola Apollonio, Paolo Giulio Franciosa
The class of Bipartite Distance Hereditary (BDH) graphs is the intersection between bipartite domino-free and chordal bipartite graphs.\ Graphs in both the latter classes have line…
Incremental DFS Trees on Arbitrary Directed Graphs
Giorgio Ausiello, Paolo G. Franciosa, Giuseppe F. Italiano +1
We present a new algorithm for maintaining a DFS tree of an arbitrary directed graph under any sequence of edge insertions. Our algorithm requires a total of time in…
On the Galois Lattice of Bipartite Distance Hereditary Graphs
Nicola Apollonio, Massimiliano Caramia, Paolo Giulio Franciosa
We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois latti…
On Resilient Graph Spanners
G. Ausiello, P. G. Franciosa, G. F. Italiano +1
We introduce and investigate a new notion of resilience in graph spanners. Let be a spanner of a graph . Roughly speaking, we say that a spanner is resilient if all its…