On rooted k-connectivity problems in quasi-bipartite digraphs

DOI10.1007/S43069-023-00285-6MaRDI QIDQ6200809zbMATH OpenOpenAlexWikidataFDO

Authors Zeev Nutov

Publication date 20 February 2024

Published in SN Operations Research Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s43069-023-00285-6

zbMATH Keywords

\(T\)-intersecting supermodular set functionsapproximation algorithmsmin-cost rooted \(k\)-edge-connectionquasi-bipartite digraphs

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Recommendations

• Approximating subset k-connectivity problems
• Rooted \(k\)-connections in digraphs
• Approximating subset \(k\)-connectivity problems
• Approximating node connectivity problems via set covers
• Approximation algorithms for minimum-cost k-(S,T) connected digraphs

Cites work

• O(^2 k/ k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• An improved approximation scheme for the Group Steiner Problem
• Approximating k-node Connected Subgraphs via Critical Graphs
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximating minimum power covers of intersecting families and directed edge-connectivity problems
• Approximating rooted Steiner networks
• Approximating source location and star survivable network problems
• Approximating Steiner networks with node-weights
• Approximating the weight of shallow Steiner trees
• Approximation Algorithms for Directed Steiner Problems
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• scientific article; zbMATH DE number 1305468 (Why is no real title available?)
• Inapproximability of survivable networks
• Matroids and integrality gaps for hypergraphic Steiner tree relaxations
• Multi-rooted greedy approximation of directed Steiner trees with applications
• Parameters of two-prover-one-round game and the hardness of connectivity problems
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
• Polylogarithmic inapproximability
• Prize-collecting survivable network design in node-weighted graphs
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• Rooted \(k\)-connections in digraphs
• Spider covers for prize-collecting network activation problem
• Steiner tree approximation via iterative randomized rounding
• Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree
• Tight approximation algorithm for connectivity augmentation problems

This page was built for publication: On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

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