{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,13]],"date-time":"2025-11-13T12:16:57Z","timestamp":1763036217079},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2007,9,27]]},"DOI":"10.1007\/s10878-007-9044-x","type":"journal-article","created":{"date-parts":[[2007,3,20]],"date-time":"2007-03-20T11:45:46Z","timestamp":1174391146000},"page":"437-453","source":"Crossref","is-referenced-by-count":46,"title":["Approximation algorithms and hardness results for\u00a0labeled connectivity problems"],"prefix":"10.1007","volume":"14","author":[{"given":"Refael","family":"Hassin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"issue":"3","key":"9044_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev AA, Sviridenko M (2004) Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J Comb Optim 8(3):307\u2013328","journal-title":"J Comb Optim"},{"issue":"3","key":"9044_CR2","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal A, Klein PN, Ravi R (1995) When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J Comput 24(3):440\u2013456","journal-title":"SIAM J Comput"},{"key":"9044_CR3","unstructured":"Arora S (November 2005) Personal communication"},{"issue":"3","key":"9044_CR4","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S Arora","year":"2003","unstructured":"Arora S, Sudan M (2003) Improved low-degree testing and its applications. Combinatorica 23(3):365\u2013426","journal-title":"Combinatorica"},{"issue":"3","key":"9044_CR5","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s00224-005-1140-7","volume":"38","author":"A Avidor","year":"2005","unstructured":"Avidor A, Zwick U (2005) Approximating MIN 2-SAT and MIN 3-SAT. Theory Comput Syst 38(3):329\u2013345","journal-title":"Theory Comput Syst"},{"key":"9044_CR6","doi-asserted-by":"crossref","unstructured":"Bellare M, Goldwasser S, Lund C, Russell A (1993) Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the 25th annual ACM symposium on theory of computing, pp 294\u2013304","DOI":"10.1145\/167088.167174"},{"issue":"2","key":"9044_CR7","doi-asserted-by":"crossref","first-page":"259","DOI":"10.7151\/dmgt.1053","volume":"17","author":"H Broersma","year":"1997","unstructured":"Broersma H, Li X (1997) Spanning trees with many or few colors in edge-colored graphs. Discuss Math Graph Theory 17(2):259\u2013269","journal-title":"Discuss Math Graph Theory"},{"key":"9044_CR8","first-page":"299","volume":"31","author":"H Broersma","year":"2005","unstructured":"Broersma H, Li X, Woeginger G, Zhang S (2005) Paths and cycles in colored graphs. Australas J Comb 31:299\u2013311","journal-title":"Australas J Comb"},{"issue":"3","key":"9044_CR9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0167-6377(02)00241-9","volume":"31","author":"T Br\u00fcggemann","year":"2003","unstructured":"Br\u00fcggemann T, Monnot J, Woeginger GJ (2003) Local search for the minimum label spanning tree problem with bounded color classes. Oper Res Lett 31(3):195\u2013201","journal-title":"Oper Res Lett"},{"key":"9044_CR10","unstructured":"Carr RD, Doddi S, Konjevod G, Marathe MV (2000) On the red-blue set cover problem. In: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms, pp 345\u2013353"},{"issue":"5","key":"9044_CR11","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0020-0190(97)00127-0","volume":"63","author":"R-S Chang","year":"1997","unstructured":"Chang R-S, Leu S-J (1997) The minimum labeling spanning trees. Inf Process Lett 63(5):277\u2013282","journal-title":"Inf Process Lett"},{"issue":"1","key":"9044_CR12","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439\u2013486","journal-title":"Ann Math"},{"key":"9044_CR13","unstructured":"Gabow HN, Stallmann MFM (1985) Efficient algorithms for graphic intersection and parity. In: Proceedings of the 12th international colloquium on automata, languages and programming, pp 210\u2013220"},{"issue":"2","key":"9044_CR14","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J Comput 24(2):296\u2013317","journal-title":"SIAM J Comput"},{"issue":"6","key":"9044_CR15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(93)90173-7","volume":"48","author":"O Goldschmidt","year":"1993","unstructured":"Goldschmidt O, Hochbaum DS, Yu G (1993) A modified greedy heuristic for the set covering problem with improved worst case bound. Inf Process Lett 48(6):305\u2013310","journal-title":"Inf Process Lett"},{"issue":"1","key":"9044_CR16","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math Oper Res 17(1):36\u201342","journal-title":"Math Oper Res"},{"issue":"3","key":"9044_CR17","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9(3):256\u2013278","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"9044_CR18","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"DR Karger","year":"1997","unstructured":"Karger DR, Motwani R, Ramkumar GDS (1997) On approximating the longest path in a graph. Algorithmica 18(1):82\u201398","journal-title":"Algorithmica"},{"issue":"1","key":"9044_CR19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller S, Moss A, Naor J (1999) The budgeted maximum coverage problem. Inf Process Lett 70(1):39\u201345","journal-title":"Inf Process Lett"},{"issue":"2","key":"9044_CR20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(98)00034-9","volume":"66","author":"SO Krumke","year":"1998","unstructured":"Krumke SO, Wirth H-C (1998) On the minimum label spanning tree problem. Inf Process Lett 66(2):81\u201385","journal-title":"Inf Process Lett"},{"issue":"5","key":"9044_CR21","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0167-6377(01)00069-4","volume":"28","author":"DH Lorenz","year":"2001","unstructured":"Lorenz DH, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper Res Lett 28(5):213\u2013219","journal-title":"Oper Res Lett"},{"key":"9044_CR22","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L (1975) On the ratio of optimal integral and fractional covers. Discret Math 13:383\u2013390","journal-title":"Discret Math"},{"issue":"1","key":"9044_CR23","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(96)00031-2","volume":"58","author":"MV Marathe","year":"1996","unstructured":"Marathe MV, Ravi SS (1996) On approximation algorithms for the minimum satisfiability problem. Inf Process Lett 58(1):23\u201329","journal-title":"Inf Process Lett"},{"key":"9044_CR24","doi-asserted-by":"crossref","unstructured":"Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th annual ACM symposium on theory of computing, pp 475\u2013484","DOI":"10.1145\/258533.258641"},{"key":"9044_CR25","doi-asserted-by":"crossref","unstructured":"Srinivasan A (2001) Distributions on level-sets with applications to approximation algorithms. In: Proceedings of the 42nd annual symposium on foundations of computer science, pp 588\u2013597","DOI":"10.1109\/SFCS.2001.959935"},{"issue":"2","key":"9044_CR26","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0020-0190(02)00230-2","volume":"84","author":"Y Wan","year":"2002","unstructured":"Wan Y, Chen G, Xu Y (2002) A note on the minimum label spanning tree. Inf Process Lett 84(2):99\u2013101","journal-title":"Inf Process Lett"},{"key":"9044_CR27","unstructured":"Wirth H-C (2001) Multicriteria approximation of network design and network upgrade problems. PhD thesis, Department of Computer Science, W\u00fcrzburg University"},{"issue":"1","key":"9044_CR28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.orl.2004.03.004","volume":"33","author":"Y Xiong","year":"2005","unstructured":"Xiong Y, Golden B, Wasil E (2005) Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem. Oper Res Lett 33(1):77\u201380","journal-title":"Oper Res Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9044-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9044-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9044-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:11Z","timestamp":1559261891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9044-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3,21]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,9,27]]}},"alternative-id":["9044"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9044-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2007,3,21]]}}}