Approximation algorithms for connected graph factors of minimum weight

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

zbMATH Keywords

approximation algorithmsedge-connectivityvertex-connectivitygraph factors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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