Fast approximation algorithms for the diameter and radius of sparse graphs
L Roditty, V Vassilevska Williams - Proceedings of the forty-fifth annual …, 2013 - dl.acm.org
The diameter and the radius of a graph are fundamental topological parameters that have
many important practical applications in real world networks. The fastest combinatorial …
many important practical applications in real world networks. The fastest combinatorial …
Lexicographic breadth first search–a survey
DG Corneil - International Workshop on Graph-Theoretic Concepts …, 2004 - Springer
Abstract Lexicographic Breadth First Search, introduced by Rose, Tarjan and Lueker for the
recognition of chordal graphs is currently the most popular graph algorithmic search …
recognition of chordal graphs is currently the most popular graph algorithmic search …
Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs
The radius and diameter are fundamental graph parameters, with several natural definitions
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …
for directed graphs. Each definition is well-motivated in a variety of applications. All versions …
On querying historical evolving graph sequences
In many applications, information is best represented as graphs. In a dynamic world,
information changes and so the graphs representing the information evolve with time. We …
information changes and so the graphs representing the information evolve with time. We …
Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
δ-Hyperbolic metric spaces have been defined by M. Gromov via a simple 4-point condition:
for any four points u, v, w, x, the two larger of the sums d (u, v)+ d (w, x), d (u, w)+ d (v, x), d …
for any four points u, v, w, x, the two larger of the sums d (u, v)+ d (w, x), d (u, w)+ d (v, x), d …
Partition refinement techniques: An interesting algorithmic tool kit
Partition refinement techniques lead to simple and efficient algorithms for various
applications: automaton minimization, string sorting… and also for algorithms on graphs. A …
applications: automaton minimization, string sorting… and also for algorithms on graphs. A …
On computing the diameter of real-world undirected graphs
We propose a new algorithm for the classical problem of computing the diameter of
undirected unweighted graphs, namely, the maximum distance among all the pairs of nodes …
undirected unweighted graphs, namely, the maximum distance among all the pairs of nodes …
Fast computation of empirically tight bounds for the diameter of massive graphs
The diameter of a graph is among its most basic parameters. Since a few years ago, it
moreover became a key issue to compute it for massive graphs in the context of complex …
moreover became a key issue to compute it for massive graphs in the context of complex …
[HTML][HTML] Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games
In this paper, we propose a new algorithm that computes the radius and the diameter of a
weakly connected digraph G=(V, E), by finding bounds through heuristics and improving …
weakly connected digraph G=(V, E), by finding bounds through heuristics and improving …
[HTML][HTML] Diameter determination on restricted graph families
Determining the diameter of a graph is a fundamental graph operation, yet no efficient (ie
linear or quadratic time) algorithm is known. In this paper, we examine the diameter problem …
linear or quadratic time) algorithm is known. In this paper, we examine the diameter problem …