Network design with weighted degree constraints
From MaRDI portal
Publication:429670
DOI10.1016/j.disopt.2010.05.004zbMath1241.90159OpenAlexW2114554145MaRDI QIDQ429670
Hiroshi Nagamochi, Takuro Fukunaga
Publication date: 20 June 2012
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/128835
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (4)
Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Degree constrained node-connectivity problems ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ Global optimization of multilevel electricity market models including network design and graph partitioning
Cites Work
- Unnamed Item
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
- Geometric algorithms and combinatorial optimization
- Spanning trees with minimum weighted degrees
- What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- Degree Bounded Matroids and Submodular Flows
- Approximating Directed Weighted-Degree Constrained Networks
- Approximating minimum bounded degree spanning trees to within one of optimal
- Survivable Network Design with Degree or Order Constraints
- Additive Guarantees for Degree-Bounded Directed Network Design
- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Many birds with one stone
- Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds
This page was built for publication: Network design with weighted degree constraints