A lower bound for the steiner tree problem in directed graphs

DOI10.1002/NET.3230200606MaRDI QIDQ5753759zbMATH OpenOpenAlexFDO

Authors Weiguo Liu

Publication date 1990

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230200606

zbMATH Keywords

directed graphsdual ascent algorithmlower boundminimum Steiner tree problemprojection method

Mathematics Subject Classification ID

Trees (05C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Facets of two Steiner arborescence polyhedra
• scientific article; zbMATH DE number 4089579
• A dual ascent approach for steiner tree problems on a directed graph
• Directed Steiner Tree Problem On A Graph: Models, Relaxations And Algorithms

Cites work

• Optimum branchings

Cited in

(16)

• A constrained Steiner tree problem
• An approach for the Steiner problem in directed graphs
• Facets of two Steiner arborescence polyhedra
• Worst-case performance of Wong's Steiner tree heuristic
• A dual ascent approach for steiner tree problems on a directed graph
• scientific article; zbMATH DE number 2044939 (Why is no real title available?)
• scientific article; zbMATH DE number 1532673 (Why is no real title available?)
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• scientific article; zbMATH DE number 2230205 (Why is no real title available?)
• Heuristic algorithms for packing of multiple-group multicasting
• Optimal connected subgraphs: Integer programming formulations and polyhedra
• Solving Steiner trees: Recent advances, challenges, and perspectives
• The average solution of a TSP instance in a graph
• An extended formulation with valid inequalities for the capacitated Steiner arborescence problem
• A factoring approach for the Steiner tree problem in undirected networks

This page was built for publication: A lower bound for the steiner tree problem in directed graphs

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