Changes between Initial Version and Version 2 of Ticket #29431


Ignore:
Timestamp:
03/30/20 20:08:26 (18 months ago)
Author:
gh-ArchitWagle
Comment:

New commits:

c822d97added the new certificate based radius algorithm
590904aMerge branch 'radius_certificate' into t/29431/certificate_based_radius_for_undirected_unweighed_graphs

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #29431

    • Property Component changed from PLEASE CHANGE to graph theory
    • Property Branch changed from to u/gh-ArchitWagle/certificate_based_radius_for_undirected_unweighed_graphs
    • Property Keywords graph gsoc radius added
    • Property Commit changed from to 590904a2561944a846218bb06aa0f551dbe261fd
    • Property Type changed from PLEASE CHANGE to enhancement
  • Ticket #29431 – Description

    initial v2  
     1This ticket implements the radius algorithm given in http://arxiv.org/abs/1803.04660
     2
     3It performs very well
     4
     5I am currently working on this, it is not commented yet and I want to run more tests, but the code seems to work on all the examples I tried
     6
     7
     8{{{
     9: G = Graph(4)                           
     10....: while not G.is_connected():
     11....:     G = graphs.RandomGNP(10000,0.008)
     12....:     
     13
     14sage: %time G.radius()
     15CPU times: user 23min 30s, sys: 4min 9s, total: 27min 39s
     16Wall time: 27min 39s
     173
     18
     19sage: %time G.radius(algorithm="certificate")
     20CPU times: user 231 ms, sys: 4.38 ms, total: 236 ms
     213
     22}}}