#13808: Gromov hyperbolicity of graphs
----------------------------------------+-----------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.6
Component: graph theory | Resolution:
Keywords: graph, hyperbolicity | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
----------------------------------------+-----------------------------------
Changes (by dcoudert):
* status: needs_work => needs_review
Old description:
> This patch implements algorithms for computing the Gromov hyperbolicity
> of a graph. Although the worst case time complexity is in `O(n^4)`, the
> proposed implementation performs quite well in practice. It has been used
> on graphs with more than 10.000 vertices.
New description:
This patch implements algorithms for computing the Gromov hyperbolicity of
a graph. Although the worst case time complexity is in `O(n^4)`, the
proposed implementation performs quite well in practice. It has been used
on graphs with more than 10.000 vertices.
APPLY:
* [attachment:trac_13808-v2.patch]
--
Comment:
Hello,
I have fully revised the patch. I have merged both patches into a new one
to simplify the process. I have removed the
{{{_reduce_biconnected_graph}}} and {{{good_core_decomposition}}} methods
and added a new one: {{{elimination_buckets}}}, where a bucket is
understood as a set of vertices that can be eliminated as soon as the
lower equals the index of the bucket. So far, this new function only
identifies vertices that can be eliminated as soon as we know that the
lower bound is 1. The code contains all the machinery to handle larger
values, but I don't have good heuristic/algorithm ready to identify
vertices that can be eliminated for 2 (only slow and not efficient
methods). I propose to let this part for a future patch. This one is
already huge...
The doc coverage is now 100%.
Should be better now.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13808#comment:5>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
