]]>Given a connected graph G of m edges and n vertices, we consider the basic problem of listing all the choices of k vertex-disjoint st-paths, for any two input vertices s,t of G and a positive integer k. Our algorithms take O(m) time per solution, using O(m) space and requiring O(F_k(G)) setup time, where F_k(G) = O(m min{k, n^{2/3} log n, sqrt{m} log n} ) is the cost of running a max-flow algorithm on~G to compute a flow of size k. The proposed techniques are simple and apply to other related listing problems as discussed in the paper.

]]>An orientation of an undirected graph is obtained by assigning a direction to each of its edges. It is called cyclic when a directed cycle appears, and acyclic otherwise. We study efficient algorithms for enumerating the orientations of an undirected graph. To get the full picture, we consider both the cases of acyclic and cyclic orientations, under some rules specifying which nodes are the sources (i.e. their incident edges are all directed outwards). Our enumeration algorithms use linear space and provide new bounds for the delay, which is the maximum elapsed time between the output of any two consecutively listed solutions. We obtain a delay of O(m) for acyclic orientations and Õ(m) for cyclic ones. When just a single source is specified, these delays become O(m⋅n) and O(m⋅h+h3), respectively, where h is the girth of the graph without the given source. When multiple sources are specified, the delays are the same as in the single source case.

The paper has been a joint work with Alessio Conte, Roberto Grossi, Takeaki Uno and Luca Versari. Below the abstract.

]]>An independent set is a set of nodes in a graph such that no two of them are adjacent. It is maximal if there is no node outside the independent set that may join it. Listing maximal independent sets in graphs can be applied, for example, to sample nodes belonging to different communities or clusters in network analysis and document clustering. The problem has a rich history as it is related to maximal cliques, dominance sets, minimum vertex covers and 3-colorings in graphs. We are interested in reducing the delay, which is the worst-case time between any two consecutively output solutions, and the memory footprint, which is the additional working space behind the read-only input graph.

A preliminar version appeared at COMPLEX NETWORK 2016, while the final version is now published on Journal Online Social Networks and Media. Here is the abstract:

]]>A unique feature of cryptocurrencies such as Bitcoin is that the blockchain containing all the economic transactions is publicly available. This makes it possible to obtain insights in the behaviour of the users through an analysis of the topological properties of the users graph which is derived from the Bitcoin transaction graph through clustering heuristics. In a previous work, we have analysed the users graph and discovered that the graph is not a small world, due to the presence of outliers in the in-degree frequency distribution of the nodes and of a high diameter, in spite of a small average distance between the nodes of the graph. In this paper, we explain our findings, showing that these structural properties of the network are due to peculiar unusual patterns in the users graph. As a further remark, we argue that these patterns are probably due to artificial users behaviours and not strictly related to normal economic interactions.

Here below the abstract:

]]>Bitcoin is a novel decentralized cryptocurrency system which has recently received a great attention from a wider audience. An interesting and unique feature of this system is that the complete list of all the transactions occurred from its inception is publicly available. This enables the investigation of funds movements to uncover interesting properties of the Bitcoin economy. In this paper we present a set of analyses of the user graph, i.e. the graph obtained by an heuristic clustering of the graph of Bitcoin transactions. Our analyses consider an up-to-date Bitcoin blockchain, as in December 2015, after the exponential explosion of the number of transactions occurred in the last two years. The set of analyses we defined includes, among others, the analysis of the time evolution of Bitcoin network, the verification of the “rich get richer” conjecture and the detection of the nodes which are critical for the network connectivity.

These are shorten versions of the original books by Runestone Interactive. This version has been modified by me for the lectures of Laboratorio di Algoritmi at Informatica Umanistica, University of Pisa. I modified the original version according to GNU Free Documentation License, Version 1.3. I am redistributing the new material under the same License. The original Forward, Prefaces, and Contributor List can be accessed at the end of the table of contents.

Check out the table of contents for basic programming or the one for algorithms and data structures.

Benefits of this book:

– You can experiment with activecode examples right in the book

– You can do your homework right in the textbook.

– Interactive questions make sure that you are on track and help you focus.

– Codelens helps you develop a mental model of how Python works.

Here below the abstract:

]]>Due to the sheer size of real-world networks, delay and space become quite relevant measures for the cost of enumeration in network analytics. This paper presents efficient algorithms for listing maximum cliques in networks, providing the first sublinear-space bounds with guaranteed delay per enumerated clique, thus comparing favorably with the known literature.

A connected road network with N nodes and L edges has K \leq L edges identified as one-way roads. In a feasible direction, these one-way roads are assigned a direction each, so that every node can reach any other [Robbins ’39]. Using O(L) preprocessing time and space usage, it is shown that all feasible directions can be found in O(K) amortized time each.

To do so, we give a new algorithm that lists all the strong orientations of an undirected connected graph with $m$ edges in O(m) amortized time each, using O(m) space.

The cost can be deamortized to obtain O(m) delay with O(m^2) preprocessing time and space.

Thanks to my coauthors: Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari

]]>Latin American Theoretical Informatics Symposium, LATIN 2016 to be held in Ensenada, Mexico (April 11-15, 2016).

The abstract follows.

We study enumeration problems for the acyclic orientations of an undirected graph with n nodes and m edges, where each edge must be assigned a direction so that the resulting directed graph is acyclic. When the acyclic orientations have single or multiple sources specified as input along with the graph, our algorithm is the first one to provide guaranteed bounds, giving new bounds with a delay of O(m n) time per solution and O(m+n) working space. When no sources are specified, our algorithm improves over previous work by reducing the delay from O(m n) to O(m) time, and is the first ones with linear delay.

Thanks to all my coauthors: Alessio Conte, Roberto Grossi, and Romeo Rizzi.

]]>