#12743: Addition of reduction rules as pre-processing of the vertex cover
function
---------------------------------+------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.0
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: David Coudert | Merged in:
Dependencies: | Stopgaps:
---------------------------------+------------------------------------------
Changes (by dcoudert):
* status: new => needs_review
Old description:
> 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
> 1. the neighbor of a vertex of degree 1 is in the cover
> 1. if the neighbors of a degree 2 vertex are incident, they are in the
> cover
> 1. if the two neighbors v,w of a degree 2 vertex u are not incident,
> then either u is in the cover or v and w 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.
New description:
This patch adds basic reduction rules as a pre-processing of the vertex
cover function. These reduction rules are the 4 basic 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
1. the neighbor of a vertex of degree 1 is in the cover
1. if the neighbors of a degree 2 vertex are incident, they are in the
cover
1. if the two neighbors v,w of a degree 2 vertex u are not incident, then
either u is in the cover or v and w 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#comment:2>
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.
