#12743: Addition of reduction rules as pre-processing of the vertex cover
function
----------------------------+-----------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.0
Component: graph theory | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors: David Coudert
Merged in: | Dependencies:
Stopgaps: |
----------------------------+-----------------------------------------------
This patch adds basic reduction rules as a pre-processing of the vertex
cover function. These reduction rules are the 3 first rules described for
instance in
http://people.scs.carleton.ca/~dehne/projects/clustalxp/ACFLSS.pdf, that
is: (1) vertices of degree 0 are not part of the cover, (2) the neighbor
of a vertex of degree 1 is in the cover, and (3) if the neighbors of a
degree 2 vertex are incident, they are in the cover.
This is particularly useful for sparse graphs.
More advanced reduction rules can also be considered (crown
decompositions, etc.) but are not part of this patch.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743>
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.
