#18839: Boost Dominator Tree
-------------------------------------+-------------------------------------
Reporter: borassi | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Dominator tree, | Merged in:
Boost | Reviewers: Nathann Cohen, David
Authors: Michele Borassi | Coudert
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/borassi/boost_dominator_tree | 512cfdf27fc1bd53f0bc3e06ba032fd23895ac01
Dependencies: #18811, #18564 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dcoudert):
> Yes, it is: if the input is undirected, the dominator tree is a star if
and only the if the graph is biconnected. In a Barabasi-Albert graph, the
minimum degree is 2, so I believe it is.
So for undirected graphs, we can first test if is it connected. If true,
then we can directly construct and return the star (or the dict) without
using boost, right? If False, then what's the output ?
What for directed graphs?
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/18839#comment:30>
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.
