Opened 13 months ago
Closed 7 months ago
#29431 closed enhancement (duplicate)
certificate based radius for undirected unweighed graphs
Reported by:  ghArchitWagle  Owned by:  

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  graph theory  Keywords:  graph, gsoc, radius 
Cc:  Merged in:  
Authors:  Reviewers:  David Coudert  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghArchitWagle/certificate_based_radius_for_undirected_unweighed_graphs (Commits, GitHub, GitLab)  Commit:  6dd478d063b40493ccc136831acfebfa1c92325c 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket implements the radius algorithm given in http://arxiv.org/abs/1803.04660
It performs very well
( >90% reduction in execution time on all graphs I tried)
: G = Graph(4) ....: while not G.is_connected(): ....: G = graphs.RandomGNP(10000,0.008) ....: sage: %time G.radius() CPU times: user 23min 30s, sys: 4min 9s, total: 27min 39s Wall time: 27min 39s 3 sage: %time G.radius(algorithm="radiuscertificate") CPU times: user 231 ms, sys: 4.38 ms, total: 236 ms 3
Change History (10)
comment:1 Changed 13 months ago by
 Branch set to u/ghArchitWagle/certificate_based_radius_for_undirected_unweighed_graphs
comment:2 Changed 13 months ago by
 Commit set to 590904a2561944a846218bb06aa0f551dbe261fd
 Component changed from PLEASE CHANGE to graph theory
 Description modified (diff)
 Keywords graph gsoc radius added
 Type changed from PLEASE CHANGE to enhancement
comment:3 Changed 13 months ago by
 Commit changed from 590904a2561944a846218bb06aa0f551dbe261fd to 6dd478d063b40493ccc136831acfebfa1c92325c
Branch pushed to git repo; I updated commit sha1. New commits:
6dd478d  Added commments, docs and modifications to handle cases like unconnected graph

comment:4 Changed 13 months ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:5 Changed 13 months ago by
 Description modified (diff)
comment:6 Changed 12 months ago by
 Milestone changed from sage9.1 to sage9.2
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:7 Changed 11 months ago by
What is the relation with #29715? It looks to me like they should be combined somehow, or one should be closed as a duplicate.
comment:8 Changed 10 months ago by
 Milestone changed from sage9.2 to sageduplicate/invalid/wontfix
The algorithm has been implemented for both weighted and unweighted undirected graphs in #29715.
comment:9 Changed 8 months ago by
 Reviewers set to David Coudert
 Status changed from needs_review to positive_review
This ticket can be closed.
comment:10 Changed 7 months ago by
 Resolution set to duplicate
 Status changed from positive_review to closed
New commits:
added the new certificate based radius algorithm
Merge branch 'radius_certificate' into t/29431/certificate_based_radius_for_undirected_unweighed_graphs