Directed Steiner trees with diffusion costs

DOI10.1007/S10878-015-9925-3MaRDI QIDQ346492zbMATH OpenOpenAlexFDO

Authors Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz, D. Barth

Publication date 29 November 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9925-3

zbMATH Keywords

approximationparameterized complexitydiffusing nodedirected Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Directed Steiner tree with branching constraint
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes
• Steiner problems with limited number of branching nodes
• scientific article; zbMATH DE number 1303557
• Multi-rooted greedy approximation of directed Steiner trees with applications

Cites work

• scientific article; zbMATH DE number 1303557 (Why is no real title available?)
• scientific article; zbMATH DE number 2086635 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• scientific article; zbMATH DE number 2209521 (Why is no real title available?)
• A fast algorithm for Steiner trees
• A note on distributed multicast routing in point-to-point networks
• A note on optical network with nonsplitting nodes
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A threshold of ln n for approximating set cover
• An approximation for minimum multicast route in optical networks with nonsplitting nodes
• An improved approximation scheme for the Group Steiner Problem
• Approximability of the minimum Steiner cycle problem
• Directed Steiner tree with branching constraint
• Finding optimum branchings
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Polylogarithmic inapproximability
• Reducibility among combinatorial problems
• Steiner problems with limited number of branching nodes
• Steiner tree problems in telecommunications
• The Steiner cycle polytope
• The steiner problem in graphs

Cited in

(10)

• Clearing directed subgraphs by mobile agents. Variations on covering with paths
• On the computational difficulty of the terminal connection problem
• Steiner problems with limited number of branching nodes
• On the terminal connection problem
• Directed Steiner tree with branching constraint
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• A multivariate analysis of the strict terminal connection problem
• Optimisation of electrical network configuration: complexity and algorithms for ring topologies
• Genetic algorithm and tabu search algorithm for solving the static manycast RWA problem in optical networks
• An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes

Describes a project that uses

Uses Software

• SteinLib
• Algorithm 97

This page was built for publication: Directed Steiner trees with diffusion costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346492)