Estructura de datos avanzadas : clases disjuntas, montículos, árboles de búsqueda

En aquest treball s'amplia la implementació en Java de les estructures de dades iniciada per Esteve Mariné, utilitzant el seu disseny bàsic. Concretament, s'ha fet la programació de les estructures de a) classes disjuntes, utilitzant els algorismes de llistes encadenades i amb estructura d'arbre, b) monticles, amb els algorismes binari, binomial i de Fibonacci, i c) arbres de recerca basats en l'algorisme d'arbre binari vermell-negre, el qual complementa els dos ja existents amb algorismes d'encadenaments i AVL. Per a examinar l'evolució de les estructures, s'ha preparat un visualitzador gràfic interactiu amb l'usuari que permet fer les operacions bàsiques de l'estructura. Amb aquest entorn és possible desar les estructures, tornar a reproduir-les i desfer i tornar a repetir les operacions fetes sobre l'estructura. Finalment, aporta una metodologia, amb visualització mitjançant gràfics, de l'avaluació comparativa dels algorismes implementats, que permet modificar els paràmetres d'avaluació com ara nombre d'elements que s'han de tractar, algorismes que s'han de comparar i nombre de repeticions. Les dades obtingudes es poden exportar per a analitzar-les posteriorment.

A sharp concentration inequality with applications

We present a new general concentration-of-measure inequality and illustrate its power by applications in random combinatorics. The results find direct applications in some problems of learning theory.

Reconstruction of networks from their betweenness centrality

In this paper we study the reconstruction of a network topology from the values of its betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. We consider a simple metaheuristic, simulated annealing, as the combinatorial optimization method to generate the network from the values of the betweenness centrality. We compare the performance of this technique when reconstructing different categories of networks –random, regular, small-world, scale-free and clustered–. We show that the method allows an exact reconstruction of small networks and leads to good topological approximations in the case of networks with larger orders. The method can be used to generate a quasi-optimal topology fora communication network from a list with the values of the maximum allowable traffic for each node.

A note on the degree sequences of graphs with restrictions

Degree sequences of some types of graphs will be studied and characterizedin this paper.

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.