Changes between Initial Version and Version 1 of Ticket #23210


Ignore:
Timestamp:
06/10/17 18:45:32 (5 years ago)
Author:
dcoudert
Comment:

New commits:

e1ca86etrac #23210: add method immediate_dominators to DiGraph
1b4a759trac #23210: add method strong_articulation_points to DiGraph
59192bbtrac #23210: add entry to module documentation
e054cddtrac #23210: biblio and documentation

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #23210

    • Property Status changed from new to needs_review
    • Property Commit changed from to e054cdde472974fc554dd1779a95ef17589ed89c
    • Property Branch changed from to u/dcoudert/23210
  • Ticket #23210 – Description

    initial v1  
    11Adds methods `immediate_dominators` and `strong_articulation_points` for directed graphs.
     2* The `immediate_dominators` is essentially the same as the NetworkX method. I tried to implement more recent algorithms [1], but the running times were not so good.
     3* The `strong_articulation_points` is as presented in [2].
     4
     5I have not included the `strong_bridges` method.
     6----
     7
     8[1] Loukas Georgiadis. Linear-Time Algorithms for Dominators and Related Problems, PhD thesis, Princetown University, (2005). ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
     9
     10[2] Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science, 447, 74–84 (2012).