#17905: Dominating set in directed Graphs not correct
-------------------------------------+-------------------------------------
Reporter: Mantis | Owner:
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.6
Component: graph theory | Resolution:
Keywords: dominating_set, | Merged in:
Graphs, Directed Graphs | Reviewers:
Authors: Sergios Lenis | Work issues:
Report Upstream: N/A | Commit:
Branch: | 3ff2fcfc5d6ebf92b553c5222383c2b139df64e6
u/Mantis/dominating_set_in_directed_graphs_not_correct| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by dcoudert):
* status: needs_review => needs_work
Comment:
Hello,
What you propose is correct. However, I would prefer this formulation.
{{{
# For any vertex v, one of its neighbors or v itself is in
# the minimum dominating set. If g is a DiGraph, we use the
# in-neighborhood of v instead.
neighbor_iterator = g.neighbor_in_iterator if g.is_directed() else
g.neighbor_iterator
for v in g.vertex_iterator():
p.add_constraint(int(not total)*b[v]+p.sum([b[u] for u in
neighbor_iterator(v)]), min=1)
}}}
For the doc test, you can add a reference to this ticket as follows. Also,
you should add an empty line before the `sage: ` lines. So this could be:
{{{
The dominating set of a DiGraph is different from the dominating set of
its underlying Graph (modification introduced in :trac:`17905`) ::
sage: g = digraphs.Path(3)
sage: len(g.dominating_set())
2
sage: gg = Graph(g)
sage: gg.is_isomorphic(graphs.PathGraph(3))
True
sage: len(gg.dominating_set())
1
}}}
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17905#comment:5>
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/d/optout.
