{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:41:22Z","timestamp":1777444882692,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0222-z","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T16:12:54Z","timestamp":1480349574000},"page":"708-741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Secluded Connectivity Problems"],"prefix":"10.1007","volume":"79","author":[{"given":"Shiri","family":"Chechik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. P.","family":"Johnson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,28]]},"reference":[{"key":"222_CR1","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: CCC, pp. 74\u201380 (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"222_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: STOC, pp. 226\u2013234 (1993)","DOI":"10.1145\/167088.167161"},{"key":"222_CR3","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11, 1\u201322 (1993)","journal-title":"Acta Cybern."},{"key":"222_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth: structure and algorithms. In: SIROCCO, pp. 11\u201325 (2007)","DOI":"10.1007\/978-3-540-72951-8_3"},{"key":"222_CR5","unstructured":"Carr, R.D., Doddi, S., Konjevod, G., Marathe, M.V.: On the red-blue set cover problem. In: SODA, pp. 345\u2013353 (2000)"},{"key":"222_CR6","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1109\/TMC.2009.147","volume":"9","author":"A Chen","year":"2010","unstructured":"Chen, A., Kumar, S., Lai, T.-H.: Local barrier coverage in wireless sensor networks. IEEE Tr. Mob. Comput. 9, 491\u2013504 (2010)","journal-title":"IEEE Tr. Mob. Comput."},{"key":"222_CR7","doi-asserted-by":"crossref","unstructured":"Chimani, M., Mutzel, P., Zey, B.: Improved steiner tree algorithms for bounded treewidth. In: IWOCA, pp. 374\u2013386 (2011)","DOI":"10.1007\/978-3-642-25011-8_30"},{"key":"222_CR8","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.ipl.2003.11.007","volume":"89","author":"I Dinur","year":"2004","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating label-cover. IPL 89, 247\u2013254 (2004)","journal-title":"IPL"},{"key":"222_CR9","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"222_CR10","first-page":"727","volume":"76","author":"MR Fellows","year":"2010","unstructured":"Fellows, M.R., Guo, J., Kanj, I.A.: The parameterized complexity of some minimum label problems. JCSS 76, 727\u2013740 (2010)","journal-title":"JCSS"},{"key":"222_CR11","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"222_CR12","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s10878-007-9044-x","volume":"14","author":"R Hassin","year":"2007","unstructured":"Hassin, R., Monnot, J., Segev, D.: Approximation algorithms and hardness results for labeled connectivity problems. J. Comb. Optim. 14, 437\u2013453 (2007)","journal-title":"J. Comb. Optim."},{"key":"222_CR13","doi-asserted-by":"crossref","unstructured":"Johansson, A., Dell\u2019Acqua, P.: Knowledge-based probability maps for covert pathfinding. In: MIG, pp. 339\u2013350 (2010)","DOI":"10.1007\/978-3-642-16958-8_32"},{"key":"222_CR14","doi-asserted-by":"crossref","unstructured":"Johnson, M.P., Liu, O., Rabanca, G.: Secluded path via shortest path. In: SIROCCO, pp. 108\u2013120 (2014)","DOI":"10.1007\/978-3-319-09620-9_10"},{"key":"222_CR15","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"222_CR16","doi-asserted-by":"crossref","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$ \u03b5 . J. Comput. Syst. Sci. 74, 335\u2013349. Elsevier (2008)","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"222_CR17","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"PN Klein","year":"1995","unstructured":"Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted steiner trees. J. Algo. 19, 104\u2013115 (1995)","journal-title":"J. Algo."},{"key":"222_CR18","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(98)00034-9","volume":"66","author":"SO Krumke","year":"1998","unstructured":"Krumke, S.O., Wirth, H.-C.: On the minimum label spanning tree problem. IPL 66, 81\u201385 (1998)","journal-title":"IPL"},{"key":"222_CR19","doi-asserted-by":"crossref","unstructured":"Liu, B., Dousse, O., Wang, J., Saipulla, A.: Strong barrier coverage of wireless sensor networks. In: MobiHoc, pp. 411\u2013420 (2008)","DOI":"10.1145\/1374618.1374673"},{"key":"222_CR20","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1017\/S0263574706002931","volume":"24","author":"M Marzouqi","year":"2006","unstructured":"Marzouqi, M., Jarvis, R.: New visibility-based path-planning approach for covert robotic navigation. Robotica 24, 759\u2013773 (2006)","journal-title":"Robotica"},{"key":"222_CR21","doi-asserted-by":"crossref","unstructured":"Marzouqi, M., Jarvis, R.: Robotic covert path planning: a survey. In: RAM, pp. 77\u201382 (2011)","DOI":"10.1109\/RAMECH.2011.6070460"},{"key":"222_CR22","doi-asserted-by":"crossref","unstructured":"Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.B.: Coverage problems in wireless ad-hoc sensor networks. In: INFOCOM, pp. 1380\u20131387 (2001)","DOI":"10.1109\/INFCOM.2001.916633"},{"key":"222_CR23","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.ipl.2005.06.009","volume":"96","author":"J Monnot","year":"2005","unstructured":"Monnot, J.: The labeled perfect matching in bipartite graphs. IPL 96, 81\u201388 (2005)","journal-title":"IPL"},{"key":"222_CR24","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jda.2006.03.008","volume":"5","author":"D Peleg","year":"2007","unstructured":"Peleg, D.: Approximation algorithms for the label-cover $$_{{\\rm max}}$$ max and red-blue set cover problems. J. Discrete Algo. 5, 55\u201364 (2007)","journal-title":"J. Discrete Algo."},{"key":"222_CR25","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algo 7, 309\u2013322 (1986)","journal-title":"J. Algo"},{"key":"222_CR26","unstructured":"Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: INFOCOM, pp. 2658\u20132669 (2005)"},{"key":"222_CR27","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/s10878-009-9222-0","volume":"21","author":"P Zhang","year":"2011","unstructured":"Zhang, P., Cai, J.Y., Tang, L., Zhao, W.: Approximation and hardness results for label cut and related problems. J. Comb. Optim. 21, 192\u2013208 (2011)","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0222-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0222-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0222-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T22:17:14Z","timestamp":1749766634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0222-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,28]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["222"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0222-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,28]]}}}