{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T01:16:14Z","timestamp":1648689374049},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:p> We study a maximization problem for geometric network design. Given a set of [Formula: see text] compact neighborhoods in [Formula: see text], select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here, we give an approximation algorithm with ratio [Formula: see text], which represents the first, albeit small, improvement beyond [Formula: see text]. While we suspect that the problem is NP-hard already in the plane, this issue remains open. <\/jats:p>","DOI":"10.1142\/s1793830920500676","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T03:25:45Z","timestamp":1591241145000},"page":"2050067","source":"Crossref","is-referenced-by-count":0,"title":["On the longest spanning tree with neighborhoods"],"prefix":"10.1142","volume":"12","author":[{"given":"Ke","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Wisconsin\u2013Milwaukee, Milwaukee, Wisconsin, USA"}]},{"given":"Adrian","family":"Dumitrescu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Wisconsin\u2013Milwaukee, Milwaukee, Wisconsin, USA"}]}],"member":"219","published-online":{"date-parts":[[2020,7,1]]},"reference":[{"key":"S1793830920500676BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90001-9"},{"key":"S1793830920500676BIB002","doi-asserted-by":"publisher","DOI":"10.3233\/FI-1995-2245"},{"key":"S1793830920500676BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"S1793830920500676BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876640"},{"key":"S1793830920500676BIB005","first-page":"296","volume-title":"Approximation Algorithms for NP-hard Problems d","author":"Bern M.","year":"1997"},{"key":"S1793830920500676BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90040-8"},{"key":"S1793830920500676BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0482-x"},{"key":"S1793830920500676BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-014-9591-3"},{"key":"S1793830920500676BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9277-9"},{"key":"S1793830920500676BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50010-3"},{"key":"S1793830920500676BIB011","first-page":"337","volume-title":"Proc. 10th Annual ACM-SIAM Symp. Discrete Algorithms","author":"Fekete S.","year":"1999"},{"key":"S1793830920500676BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"key":"S1793830920500676BIB013","first-page":"811","volume-title":"Handbook of Computational Geometry","author":"Mitchell J. S. B.","year":"2017","edition":"3"},{"key":"S1793830920500676BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840396"},{"key":"S1793830920500676BIB015","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203"},{"key":"S1793830920500676BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"S1793830920500676BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0029-8"},{"key":"S1793830920500676BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(93)90144-3"},{"key":"S1793830920500676BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(82)90046-0"},{"key":"S1793830920500676BIB020","series-title":"LNCS","first-page":"306","volume-title":"Proc. 3rd Int. Conf. Algor. Aspects in Information and Management (AAIM)","volume":"4508","author":"Yang Y.","year":"2007"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830920500676","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,2]],"date-time":"2020-10-02T07:24:03Z","timestamp":1601623443000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830920500676"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,1]]},"references-count":20,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.1142\/S1793830920500676"],"URL":"https:\/\/doi.org\/10.1142\/s1793830920500676","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,1]]}}}