Degree constrained node-connectivity problems
DOI10.1007/S00453-013-9849-1zbMATH Open1314.68237OpenAlexW1983217642MaRDI QIDQ486998FDOQ486998
Authors: Zeev Nutov 
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9849-1
Recommendations
- Degree-constrained node-connectivity
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
- Survivable network design with degree or order constraints
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- Network-design with degree constraints
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40) Network design and communication in computer systems (68M10)
Cites Work
- An application of submodular flows
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
- Improved Approximation Algorithms for Uniform Connectivity Problems
- Rooted \(k\)-connections in digraphs
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Degree-constrained node-connectivity
- Iterative methods in combinatorial optimization.
- Network-design with degree constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- Improved algorithm for degree bounded survivable network design problem
- Survivable network design with degree or order constraints
- Additive guarantees for degree-bounded directed network design
- Title not available (Why is that?)
- Approximating directed weighted-degree constrained networks
- Approximating node connectivity problems via set covers
- Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
- Minimal edge-coverings of pairs of sets
- Network design with weighted degree constraints
- Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
- Degree bounded network design with metric costs
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- Network design via iterative rounding of setpair relaxations
Cited In (11)
- Network Design with Edge-Connectivity and Degree Constraints
- Improved algorithm for degree bounded survivable network design problem
- Network-design with degree constraints
- Degree-constrained node-connectivity
- On some network design problems with degree constraints
- Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
- Approximating Directed Weighted-Degree Constrained Networks
- The connected critical node problem
- Complexity of some graph-based bounds on the probability of a union of events
- Approximating directed weighted-degree constrained networks
- On the approximability of some degree-constrained subgraph problems
This page was built for publication: Degree constrained node-connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q486998)
