{"entities":{"Q896300":{"pageid":898148,"ns":120,"title":"Item:Q896300","lastrevid":52411253,"modified":"2026-01-22T14:21:43Z","type":"item","id":"Q896300","labels":{"en":{"language":"en","value":"A unified algorithm for degree bounded survivable network design"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6518246"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$8F4D6E4B-12AF-4881-9A6C-C320559C9490","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e609602b76c7027e93da33f32b932ff16d7a2f0c","datavalue":{"value":{"text":"A unified algorithm for degree bounded survivable network design","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q896300$865B63E6-F29B-4F56-90F7-50D75CDC0D70","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"73a38a354ea7b1fb2a1b5db989efceb03531dd1f","datavalue":{"value":"1338.68292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$267CF16A-BA27-42C1-90C5-0BDB6C7ADD46","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86f340c200ea4ef58b9ef42ffeef32d598716e23","datavalue":{"value":{"entity-type":"item","numeric-id":715087,"id":"Q715087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$7B0B2A53-6CC8-4F82-820D-4374CD331A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"593ba66a87340241778f2a92a83c4ac736c35c48","datavalue":{"value":{"entity-type":"item","numeric-id":195810,"id":"Q195810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$DB88E0BB-976D-46CE-8EA2-C894A8530423","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$350B488F-0FF7-47BB-8813-1285E675EC62","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2b8734b9abc793f74f77d5198b802e2e4c98f1c9","datavalue":{"value":{"time":"+2015-12-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q896300$9E41444D-46D9-4A0B-86B1-3703D341A6DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bdf5d33422c461dbd848fc0ade33da1c145c991c","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q896300$A84A03CE-7D3F-4669-A211-934B5C834EB6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$E11791E8-2BB6-4883-8C0B-7DA99814F02E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$FFB82558-CC07-4C10-A9CC-0BDFBC24F405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$D8B8DE79-6107-4A1A-B152-73FB12D4A33B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$F037A560-B57F-4F83-8077-CF756D95C216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$1C5CFEB1-1940-4B6C-943F-188AF64EA72A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c939169bc86ec04519cd938af861d9faf010c97","datavalue":{"value":"6518246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$47D170B8-952C-494E-992A-4D5DAC521DD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q896300$5428B11A-11E0-44F4-976B-EF83D521A66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q896300$07F1DF13-DF5D-4103-AC60-0A7AD464F9B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f500218927052d88e502b78e2d941eb244f8d80","datavalue":{"value":"minimum bounded degree Steiner network","type":"string"},"datatype":"string"},"type":"statement","id":"Q896300$7F7AFDF3-9B52-4F56-8278-7324482DB5FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f9f554eb64639799bf090dd0dfa97bafd06e8c2c","datavalue":{"value":{"entity-type":"item","numeric-id":229433,"id":"Q229433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$6757CB53-FABC-45E2-881D-A7A290945F32","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$AC1BCCE8-2A63-4840-922E-0FC67D8884EE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b5eabdc229deb46dc9038c45c89002bf4748143c","datavalue":{"value":"https://doi.org/10.1007/s10107-015-0858-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q896300$56746AA1-CAA6-4480-A2E8-9D11C803B291","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a99cd90c6b62fe03f13dcf2b9c33894a1c9572bf","datavalue":{"value":"W2126340073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$3B6C6746-545D-4064-83F8-8051393A9BBF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58bd89953507138840b0098c9ef357c473acd1f4","datavalue":{"value":{"entity-type":"item","numeric-id":3586186,"id":"Q3586186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$062BD1C5-1201-4B99-B6D6-7E0107603E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5d2063c5d368eafc71691bb65f1ed793118c024","datavalue":{"value":{"entity-type":"item","numeric-id":2929700,"id":"Q2929700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$3CC5B633-C5AB-409A-B1DB-A4B51C0E0E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a562b6d0064519372190aa34203e149eb4331b8f","datavalue":{"value":{"entity-type":"item","numeric-id":858116,"id":"Q858116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$F47D1102-9CCF-4308-9F69-14EE91A5DACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a9041903a1b0dda73e34f28454bc4532b9015bb","datavalue":{"value":{"entity-type":"item","numeric-id":2496319,"id":"Q2496319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$24FC3F8C-2761-46B3-9253-50FCEB1EB6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e6e84e4180f062a41c2878c1c40442754646d52","datavalue":{"value":{"entity-type":"item","numeric-id":355516,"id":"Q355516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$F0AE5923-4A12-4EA4-A26A-20E5AF01D3CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dd6d9ae660e25cf6e630494c601c181d753df8c","datavalue":{"value":{"entity-type":"item","numeric-id":4314499,"id":"Q4314499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$AC730249-9244-4000-9777-4FA6B3619215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0200fd32d8e2dd0cce0bf933f5ad11d6ce7944c9","datavalue":{"value":{"entity-type":"item","numeric-id":3596336,"id":"Q3596336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$9CF5342D-A801-4B8E-BAF0-77D80534D8C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6adf1f1cc41e36992f9ea3fb9db7c8a6d08a719","datavalue":{"value":{"entity-type":"item","numeric-id":873648,"id":"Q873648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$2E71A4FA-DDC6-489A-94AD-408194189D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2e6295806da5f275a0d5240db41bd555302c27","datavalue":{"value":{"entity-type":"item","numeric-id":3503852,"id":"Q3503852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$E2E2FE8F-FB1F-4D83-BB90-9539A39E8769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c712a3f9cd64846c1c97fe79f4bf07e18126e405","datavalue":{"value":{"entity-type":"item","numeric-id":3575159,"id":"Q3575159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$D2FBCF9E-05E6-4AB5-B0A9-14022B83F34F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1afac2a56d85c0c834dba07c84a96b10ebb796f2","datavalue":{"value":{"entity-type":"item","numeric-id":3087101,"id":"Q3087101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$D15543C1-3156-4B12-A167-4263AB69319C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ed99b4c4554565eec0c54885af02510ae9e21db","datavalue":{"value":{"entity-type":"item","numeric-id":5408765,"id":"Q5408765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$FC25D72D-F5A5-4FB4-8300-AA6D368862AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3c5ea3c39eea2f0e1bedb6208670a1d00a24523","datavalue":{"value":{"entity-type":"item","numeric-id":3569909,"id":"Q3569909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$6DE8FFBC-BCD7-40BD-B259-404E83521F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff871892bba9ab1f15aa7ab2567d0791a7fa27fd","datavalue":{"value":{"entity-type":"item","numeric-id":2894500,"id":"Q2894500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$4698C5E3-D791-4B15-A871-4F5B987D8944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b27909206ade5b263b26b39f27c396a5a0f02bd4","datavalue":{"value":{"entity-type":"item","numeric-id":3549667,"id":"Q3549667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896300$37366825-D733-48BD-9F0B-0E27F70F5735","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a6847097717da5a8c88a9c5013c25f2da50ff138","datavalue":{"value":"10.1007/S10107-015-0858-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896300$26AEC0E1-1AF2-491A-8C9F-4CED10BC31B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"097ef1b006d0bf99eea59f49959541262b8b8f61","datavalue":{"value":{"entity-type":"item","numeric-id":5419010,"id":"Q5419010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a75071d789c64a7cc51fd16267bae21840a2c66","datavalue":{"value":{"amount":"+0.9986968636512756","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q896300$572D81D1-70B4-40A3-8B58-FAE0CF8E51FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f27145ad7fe7698ea0b818c39d60dce5cf56da4","datavalue":{"value":{"entity-type":"item","numeric-id":3569909,"id":"Q3569909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48d42422a58a4be1f9e8e13fded257d23c3bf88c","datavalue":{"value":{"amount":"+0.9003868103027344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q896300$710FE57A-C09F-40C6-B8A1-47F7A37FB8DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6e7be161238a0945c83131bc89a9211c3d1a024","datavalue":{"value":{"entity-type":"item","numeric-id":5408765,"id":"Q5408765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cce4338a066c6dbd90fa7f77748c99c2aa170337","datavalue":{"value":{"amount":"+0.883260190486908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q896300$C67952F9-3C85-4799-A2ED-4213661727E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a470317d7889ae09f6453bb0dd981a89149a896","datavalue":{"value":{"entity-type":"item","numeric-id":3096090,"id":"Q3096090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f2df5a59e20bd5cdadcc2225eeb513b9b629a14","datavalue":{"value":{"amount":"+0.8489065170288086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q896300$FB395DF8-99EB-42BC-AB20-168D67A2FF85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6d188ad290230a76ef6df5b1f3b1ca1c1210d30","datavalue":{"value":{"entity-type":"item","numeric-id":3575159,"id":"Q3575159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"012931a9864490c7c26b42476de48f86d547d816","datavalue":{"value":{"amount":"+0.8447047472000122","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q896300$999C634A-5745-498B-A9BC-8758BB6275F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:896300","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:896300"}}}}}