Distributed Approximate k-Core Decomposition and Min-Max Edge Orientation: Breaking the Diameter Barrier - Département Informatique et Réseaux Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Distributed Approximate k-Core Decomposition and Min-Max Edge Orientation: Breaking the Diameter Barrier

T-H Hubert Chan
  • Fonction : Auteur
Bintao Sun
  • Fonction : Auteur

Résumé

We design distributed algorithms to compute approximate solutions for several related graph optimization problems. All our algorithms have round complexity being logarithmic in the number of nodes of the underlying graph and in particular independent of the graph diameter. By using a primal-dual approach, we develop a 2(1 +)-approximation algorithm for computing the coreness values of the nodes in the underlying graph, as well as a 2(1 +)-approximation algorithm for the min-max edge orientation problem, where the goal is to orient the edges so as to minimize the maximum weighted in-degree. We provide lower bounds showing that the aforementioned algorithms are tight both in terms of the approximation guarantee and the round complexity. Finally, motivated by the fact that the densest subset problem has an inherent dependency on the diameter of the graph, we study a weaker version that does not suffer from the same limitation.
Fichier principal
Vignette du fichier
main.pdf (571.95 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02315485 , version 1 (14-10-2019)

Identifiants

Citer

T-H Hubert Chan, Mauro Sozio, Bintao Sun. Distributed Approximate k-Core Decomposition and Min-Max Edge Orientation: Breaking the Diameter Barrier. : 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2019, Rio de Janeiro, Brazil. ⟨10.1109/IPDPS.2019.00044⟩. ⟨hal-02315485⟩
34 Consultations
307 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More