#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:
---------------------------------+------------------------------------------
Old description:
> This patch does the following
>
> 1. Moves the vertex_cover function from generic_graph.py to graph.py.
> The function is valid only for graphs and the independent_set function
> was already in graph.py.
> 1. Simplifies the independent_set function so that it calls the
> vertex_cover function.
> 1. 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.
New description:
This patch does the following
1. Moves the vertex_cover function from generic_graph.py to graph.py. The
function is valid only for graphs and the independent_set function was
already in graph.py.
1. Simplifies the independent_set function so that it calls the
vertex_cover function.
1. 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.
APPLY:
* [attachment:trac_12743_reduction_rules_for_vertex_cover.patch]
* [attachment:trac_12743-review.patch]
* [attachment:trac_12743-review2.patch]
* [attachment:trac_12743-doctest.patch]
--
Comment (by ncohen):
Patch updated !
You were right to fix this line... In order to avoid it, I added a line to
the doctests in this patch. If all is fine by you, you can set the ticket
to positive review ! `:-)`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#comment:13>
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.
