{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q896300","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q896300","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q896300","kernelVersion":"v1","immutable":true,"modified":"2026-01-22T14:21:43Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q896300","name":"A unified algorithm for degree bounded survivable network design","headline":"A unified algorithm for degree bounded survivable network design","description":"scientific article; zbMATH DE number 6518246","url":"https://portal.mardi4nfdi.de/entity/Q896300","datePublished":"2015-12-09","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q715087"},{"@id":"https://portal.mardi4nfdi.de/entity/Q195810"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q163006"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1007/S10107-015-0858-5","url":"https://doi.org/10.1007/S10107-015-0858-5"},"sameAs":["https://doi.org/10.1007/S10107-015-0858-5"],"comment":"This paper considers the minimum bounded degree Steiner network problem, where an undirected graph \\(G\\), a cost \\(c_e\\) on each edge \\(e\\), a degree bound \\(b_v\\) on each vertex \\(v\\) and a connectivity requirement \\(r_{uv}\\) for each pair of vertices \\((u,v)\\) are given and the objective is to find a Steiner network \\(H \\subseteq G\\) with minimum total cost respecting the given degree bounds on the vertices. For this problem, a polynomial-time approximation algorithm with cost at most two times the optimal value is given such that the degree on each vertex is at most equal to \\(\\min \\{ b_v + 3 r_{\\max}, 2 b_v + 2 \\}\\), where \\(r_{\\max}\\) is the maximum connectivity requirement. This improves a previous result for this problem given by the first author and \\textit{M. Singh} [SIAM J. Comput. 42, No. 6, 2217--2242 (2013; Zbl 1285.68216)]. The authors give also an example for which their algorithm fails to give a \\(2\\)-approximation algorithm with a degree on each vertex at most \\(b_v + 2\\) for the minimum bounded degree Steiner forest problem.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3586186"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2929700"},{"@id":"https://portal.mardi4nfdi.de/entity/Q858116"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2496319"},{"@id":"https://portal.mardi4nfdi.de/entity/Q355516"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4314499"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3596336"},{"@id":"https://portal.mardi4nfdi.de/entity/Q873648"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3503852"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3575159"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3087101"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5408765"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3569909"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2894500"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3549667"}]},"provenance":{"prov:generatedAtTime":"2026-01-22T14:21:43Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}