#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:
---------------------------------+------------------------------------------
Comment (by dcoudert):
Some running time examples:
{{{
sage: G = graphs.RandomTree(100)
sage: %time G.vertex_cover()
CPU times: user 0.21 s, sys: 0.00 s, total: 0.21 s
Wall time: 0.21 s
set([0, 1, 2, 5, 6, 9, 11, 12, 14, 17, 18, 19, 22, 23, 28, 29, 31, 41, 44,
46, 47, 51, 54, 56, 57, 60, 61, 63, 64, 66, 67, 70, 72, 74, 75, 76, 79,
80, 81, 82, 85, 88, 92, 96, 98])
sage: %time G.vertex_cover(reduction_rules = True)
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.04 s
set([1, 2, 5, 6, 7, 8, 9, 11, 12, 13, 14, 17, 18, 19, 21, 22, 27, 39, 41,
44, 47, 51, 53, 54, 55, 56, 60, 61, 62, 63, 65, 67, 71, 72, 74, 81, 82,
85, 88, 89, 92, 93, 95, 96, 98])
}}}
{{{
sage: G = graphs.GridGraph([10,10])
sage: %time G.vertex_cover()
CPU times: user 0.19 s, sys: 0.00 s, total: 0.19 s
Wall time: 0.19 s
set([(7, 3), (1, 3), (9, 1), (4, 8), (2, 8), (8, 0), (7, 7), (4, 6), (2,
6), (5, 1), (6, 2), (3, 7), (4, 0), (3, 1), (5, 5), (0, 6), (6, 6), (4,
4), (1, 5), (2, 2), (8, 6), (5, 3), (1, 1), (9, 7), (6, 4), (0, 0), (8,
2), (7, 1), (9, 3), (6, 0), (3, 5), (5, 9), (7, 5), (1, 9), (0, 4), (0,
8), (3, 3), (6, 8), (5, 7), (9, 9), (4, 2), (0, 2), (2, 0), (8, 8), (7,
9), (1, 7), (9, 5), (3, 9), (2, 4), (8, 4)])
sage: %time G.vertex_cover(reduction_rules = True)
CPU times: user 0.17 s, sys: 0.00 s, total: 0.17 s
Wall time: 0.17 s
set([(7, 8), (6, 9), (3, 0), (9, 8), (3, 2), (0, 7), (8, 9), (1, 6), (9,
4), (2, 5), (8, 5), (0, 3), (7, 2), (1, 2), (7, 4), (9, 0), (6, 7), (2,
9), (8, 1), (7, 6), (6, 3), (5, 6), (5, 8), (3, 6), (4, 1), (0, 1), (5,
4), (5, 0), (4, 5), (1, 4), (0, 5), (2, 1), (8, 7), (4, 9), (1, 0), (9,
6), (6, 5), (2, 7), (8, 3), (7, 0), (4, 7), (9, 2), (5, 2), (6, 1), (3,
8), (1, 8), (4, 3), (0, 9), (2, 3), (3, 4)])
}}}
{{{
sage: G = graphs.RandomGNP(200,0.01)
sage: %time G.vertex_cover(value_only = True)
CPU times: user 0.75 s, sys: 0.00 s, total: 0.75 s
Wall time: 0.76 s
72
sage: %time G.vertex_cover(reduction_rules = True, value_only=True)
CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s
Wall time: 0.10 s
72
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12743#comment:3>
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.
