#15735: a new spkg
-------------------------+-------------------------------------------------
Reporter: spurtuna | Owner: spurtuna
Type: | Status: new
enhancement | Milestone: sage-6.1
Priority: minor | Keywords: graph,hard,feedback vertex
Component: PLEASE | set
CHANGE | Authors: spurtuna
Merged in: | Report Upstream: None of the above - read trac
Reviewers: | for reasoning.
Work issues: | Branch:
Commit: | Dependencies: None
Stopgaps: |
-------------------------+-------------------------------------------------
This is pushing of a new (c/c++) spkg somewhatfptufvs.
I merge it with generic_graphs, as there is a similar algorithm for
directed graphs, even if it is not implemented in this package yet.
The somewhatfptufvs package is in attachment and in the mail. Expect to
see a new version soon that has an implementation for weighted undirected
graphs. Some documentation would be nice too.
I claim that this solver the graph problem Feedback Vertex Set, and does
so faster then the LP algorithm available. See appendix in Readme for a
benchmark written for sage notebook. (performance on weighted undirected
graphs remains to be seen)
I do not imagine this package replacing anything. All LP "genre"
implementations like the MIP, should be quite generic. They solve many
problems, and does so with small formulas.
The solver I present require constant amount of memory, no dependencies,
have reasonable build time, and there is room for reducing it's spkg size.
Usability of this package extend the usability beyond what MIP can provide
with regards to representation of weights, if not the same usability. I
have not implemented it with support for directed graphs. There are also
some limitations I find to be fitting, as in that these assumptions are
common, require not much effort, would be nothing but a new code-file if
added to package, and these assumptions are documented/todos.
I have no reason to believe that this software is not stable.
--
Ticket URL: <http://trac.sagemath.org/ticket/15735>
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/groups/opt_out.
