Directed Steiner trees with diffusion costs

DOI10.1007/S10878-015-9925-3zbMath1356.90152OpenAlexW2219735116MaRDI QIDQ346492

Cédric Bentz, Dimitri Watel, Marc-Antoine Weisser, Dominique Barith

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)

Related Items (7)

On the terminal connection problem ⋮ On the computational difficulty of the terminal connection problem ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Optimisation of electrical network configuration: complexity and algorithms for ring topologies ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Genetic algorithm and tabu search algorithm for solving the static manycast RWA problem in optical networks ⋮ A multivariate analysis of the strict terminal connection problem

Uses Software

• SteinLib
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• A note on optical network with nonsplitting nodes
• A fast algorithm for Steiner trees
• The Steiner cycle polytope
• An approximation for minimum multicast route in optical networks with nonsplitting nodes
• An improved approximation scheme for the Group Steiner Problem
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Steiner Problems with Limited Number of Branching Nodes
• Directed Steiner Tree with Branching Constraint
• A threshold of ln n for approximating set cover
• Polylogarithmic inapproximability
• Finding optimum branchings
• Reducibility among Combinatorial Problems
• The steiner problem in graphs
• A note on distributed multicast routing in point-to-point networks

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