On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
type: Item
instance of: scholarly article
title: On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
DOI: 10.1007/978-3-030-79416-3_20
author: Zeev Nutov
publication date: 2022-03-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/2009.10160
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7493540
MaRDI profile type: Publication
OpenAlex ID: W3174748938
cites work: Steiner Tree Approximation via Iterative Randomized Rounding
cites work: Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
cites work: Approximation Algorithms for Directed Steiner Problems
cites work: Prize-Collecting Survivable Network Design in Node-Weighted Graphs
cites work: Q5743494
cites work: Q4638871
cites work: An $O(\log^2{k})$-Approximation Algorithm for the $k$-Vertex Connected Spanning Subgraph Problem
cites work: Q3859792
cites work: Rooted \(k\)-connections in digraphs
cites work: A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
cites work: Spider covers for prize-collecting network activation problem
cites work: A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
cites work: Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
cites work: Matroids and integrality gaps for hypergraphic steiner tree relaxations
cites work: Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
cites work: O (log 2 k / log log k )-approximation algorithm for directed Steiner tree
cites work: Polylogarithmic inapproximability
cites work: An improved approximation scheme for the Group Steiner Problem
cites work: Multi-rooted greedy approximation of directed Steiner trees with applications
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
cites work: Approximating k-node Connected Subgraphs via Critical Graphs
cites work: Tight approximation algorithm for connectivity augmentation problems
cites work: Approximating Source Location and Star Survivable Network Problems
cites work: Approximating the weight of shallow Steiner trees
cites work: Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
cites work: Inapproximability of survivable networks
cites work: Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
cites work: Approximating Steiner Networks with Node Weights
cites work: Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
cites work: Improved approximation algorithms for minimum cost node-connectivity augmentation problems
cites work: Q4252355
cites work: A series of approximation algorithms for the acyclic directed Steiner tree problem
description: scientific article; zbMATH DE number 7493540