5 citations · 9 across the 8 of their papers we have counts for
8 papers
Non-Crossing Shortest Paths are Covered with Exactly Four Forests
Lorenzo Balzotti
Given a set of paths we define the \emph{Path Covering with Forest Number} of } (PCFN()) as the minimum size of a set of forests satisfying that every path in is…
Two New Characterizations of Path Graphs
Nicola Apollonio, Lorenzo Balzotti
Path graphs are intersection graphs of paths in a tree. We start from the characterization of path graphs by Monma and Wei [C.L.~Monma,~and~V.K.~Wei, Intersection Graphs of Paths i…
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…
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 …
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-…
Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
Lorenzo Balzotti
A path graph is the intersection graph of paths in a tree. A directed path graph is the intersection graph of paths in a directed tree. Even if path graphs and directed path graphs…
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.…
A New Characterization of Path Graphs
Nicola Apollonio, Lorenzo Balzotti
Path graphs are intersection graphs of paths in a tree.~In this paper we give a "6\ good characterization" of path graphs, namely, we prove that path graph membership is in $NP\cap…