Approximating Directed Weighted-Degree Constrained Networks

DOI10.1007/978-3-540-85363-3_18MaRDI QIDQ3541798zbMATH OpenOpenAlexFDO

Authors Zeev Nutov

Publication date 27 November 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85363-3_18

Mathematics Subject Classification ID

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

Recommendations

• Approximating directed weighted-degree constrained networks
• Network design with weighted degree constraints
• Network Design with Weighted Degree Constraints
• Additive guarantees for degree-bounded directed network design
• Degree constrained node-connectivity problems

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• Algorithms for a network design problem with crossing supermodular demands
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• scientific article; zbMATH DE number 863470 (Why is no real title available?)
• scientific article; zbMATH DE number 5485591 (Why is no real title available?)
• Many birds with one stone
• Network Design with Weighted Degree Constraints
• Small degree out‐branchings
• Survivable network design with degree or order constraints

Cited in

(9)

• Constant factor approximation for the weighted partial degree bounded edge packing problem
• On approximating the \(d\)-girth of a graph
• On Approximating the d-Girth of a Graph
• Additive guarantees for degree-bounded directed network design
• Network Design with Weighted Degree Constraints
• Network design with weighted degree constraints
• The effect of reverse edges on convergence rate of directed weighted chain network
• Approximating directed weighted-degree constrained networks
• Improved approximation algorithms for maximum lifetime problems in wireless networks

This page was built for publication: Approximating Directed Weighted-Degree Constrained Networks

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