#17647: Branch and Bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | 9b5f33e7a67218dda91bed304b5f3e2f276b389b
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by dcoudert):
* status: new => needs_review
* cc: ncohen (added)
Old description:
> This patch implements a branch and bound algorithm for computing the
> vertex separation of directed graphs, and so the pathwidth of graphs.
New description:
This patch implements a branch and bound algorithm for computing the
vertex separation of directed graphs. It can be significantly faster than
other methods already implemented. Furthermore, it can handle graphs with
more than 31 vertices, but of course the computation time could be long.
{{{
sage: from sage.graphs.graph_decompositions import vertex_separation as VS
sage: D = digraphs.RandomDirectedGNP(30,.1)
sage: %time w,l = VS.vertex_separation(D); print w
4
CPU times: user 229 ms, sys: 345 ms, total: 574 ms
Wall time: 575 ms
sage: %time w,l = VS.vertex_separation_BAB(D); print w
4
CPU times: user 1.34 ms, sys: 32 µs, total: 1.37 ms
Wall time: 1.35 ms
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:4>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
