#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 borassi):
Hellooooo!
Replying to [comment:30 dcoudert]:
> 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 ?
Well, not connected but biconnected. In any case, probably the dominator
tree in the undirected case can be found by computing biconnected
components and cut vertices. There is a linear algorithm for biconnected
components, but it is not very easy to implement, and the Boost algorithm
is O(m log m), which is not much worse than O(m). Is the linear algorithm
for BCC implemented in the hyperbolicity algorithm?
>
> What for directed graphs?
Well, it is more complicated... I heard that finding linear algorithms for
this problem is an open issue, and the Boost algorithm should be optimal.
For more information, see the Boost help page
http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/lengauer_tarjan_dominator.htm.
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18839#comment:31>
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.
