Approximation algorithms for connected graph factors of minimum weight
From MaRDI portal
Publication:1743127
DOI10.1007/s00224-016-9723-zzbMath1390.68760DBLPjournals/mst/CornelissenHMNR18OpenAlexW2552587983WikidataQ59439375 ScholiaQ59439375MaRDI QIDQ1743127
Ruben Hoeksma, Bodo Manthey, Marten Waanders, C. S. Rahul, Kamiel Cornelissen, N. S. Narayanaswamy
Publication date: 12 April 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-016-9723-z
Related Items (2)
On the complexity landscape of connected \(f\)-factor problems ⋮ Approximating bounded-degree spanning trees and connected factors with leaves
Cites Work
- Unnamed Item
- On some network design problems with degree constraints
- Network design with weighted degree constraints
- Survivable networks, linear programming relaxations and the parsimonious property
- Network design with edge-connectivity and degree constraints
- The complexity of regular subgraph recognition
- Matching theory
- Optimization, approximation, and complexity classes
- Approximating node connectivity problems via set covers
- Approximation Algorithms for k-Connected Graph Factors
- The Design of Approximation Algorithms
- Degree Bounded Network Design with Metric Costs
- Approximability of Connected Factors
- Approximation and Exact Algorithms for Special Cases of Connected f-Factors
- Approximation Algorithms for Network Design with Metric Costs
- Survivable Network Design with Degree or Order Constraints
- Heuristic analysis, linear programming and branch and bound
- Biconnectivity approximations and graph carvings
- A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
- An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
- The Traveling Salesman Problem with Distances One and Two
- Additive Approximation for Bounded Degree Survivable Network Design
- A Unified Algorithm for Degree Bounded Survivable Network Design
- Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
- A Short Proof of the Factor Theorem for Finite Graphs
This page was built for publication: Approximation algorithms for connected graph factors of minimum weight
