Shi Q, Garcia R, Flecker A, Sethi SA, Gomes C. (2018) Efficiently optimizing for dendritic connectivity on tree-structured networks in a multi-objective framework. Conference on Computation and Sustainable Society 2018.
We provide an exact and approximation algorithm based on dynamic programming and an approximation algo- rithm based on MIP for optimizing for the so-called dendritic connectivity on tree-structured networks in a multi-objective setting. Dentritic connectivity describes the degree of connectedness of a network. We con- sider different variants of dendritic connectivity to cap- ture both network connectivity with respect to long and short-to-middle distances. Our work is motivated by a problem in computational sustainability concerning the evaluation of trade-offs in ecosystem services due to the proliferation of hydropower dams throughout the Ama- zon basin. In particular, we consider trade-offs between energy production and river connectivity. River frag- mentation can dramatically affect fish migrations and other ecosystem services, such a navigation and trans- portation. In the context of river networks, different variants of dendritic connectivity are important to char- acterize the movements of different fish species and hu- man populations. Our approaches are general and can be applied to optimizing for dendritic connectivity for a variety of multi-objective problems on tree-structured networks.