4 papers · 1 filter
Shortest Path Centrality and the APSP problem via VC-dimension and Rademacher Averages
Alane M. de Lima, Murilo V. G. da Silva, André L. Vignatti
In this paper we are interested in a version of the All-pairs Shortest Paths problem (APSP) that fits neither in the exact nor in the approximate case. We define a measure of centr…
Estimating the Percolation Centrality of Large Networks through Pseudo-dimension Theory
Alane M. de Lima, Murilo V. G. da Silva, André L. Vignatti
In this work we investigate the problem of estimating the percolation centrality of every vertex in a graph. This centrality measure quantifies the importance of each vertex in a g…
Small World Model based on a Sphere Homeomorphic Geometry
Santiago Viertel, André Luís Vignatti
We define a small world model over the octahedron surface and relate its distances with those of embedded spheres, preserving constant bounded distortions. The model builds network…
Labeling Algorithm and Compact Routing Scheme for a Small World Network Model
Santiago Viertel, André Luís Vignatti
This paper defines the toroidal small world labeling problem that asks for a labeling of the vertices of a network such that the labels possess information that allows a compact ro…