A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs

DOI10.4230/LIPIcs.SWAT.2016.3zbMath1378.68194arXiv1604.08132OpenAlexW2963623089MaRDI QIDQ5369505

Jochen Könemann, Mohammad Shadravan, Zachary Friggstad

Publication date: 17 October 2017

Full work available at URL: https://arxiv.org/abs/1604.08132

zbMATH Keywords

approximation algorithmprimal-dual algorithmdirected Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

This page was built for publication: A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs