{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T11:11:17Z","timestamp":1648811477232},"reference-count":15,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,11]]},"abstract":"<jats:p> We introduce and study a new Steiner tree problem variation called the bursty Steiner tree problem where new nodes arrive into bursts. This is an online problem which becomes the well-known online Steiner tree problem if the number of nodes in each burst is exactly one and becomes the classic Steiner tree problem if all the nodes appear in a single burst. In undirected graphs, we provide a tight bound of [Formula: see text] on the competitive ratio for this problem, where [Formula: see text] is the total number of nodes to be connected and [Formula: see text] is the total number of different bursts. In directed graphs of bounded edge asymmetry [Formula: see text], we provide a competitive ratio for this problem with a gap of [Formula: see text] factor between the lower bound and the upper bound. We also show that a tight bound of [Formula: see text] on the competitive ratio can be obtained for a bursty variation of the terminal Steiner tree problem. These are the first results that provide clear performance trade-offs for a novel Steiner tree problem variation that subsumes both of its online and classic versions. <\/jats:p>","DOI":"10.1142\/s0129054117500290","type":"journal-article","created":{"date-parts":[[2018,2,23]],"date-time":"2018-02-23T03:50:52Z","timestamp":1519357852000},"page":"869-887","source":"Crossref","is-referenced-by-count":0,"title":["The Bursty Steiner Tree Problem"],"prefix":"10.1142","volume":"28","author":[{"given":"Gokarna","family":"Sharma","sequence":"first","affiliation":[{"name":"Department of Computer Science, Kent State University, Kent, OH 44242, USA"}]},{"given":"Costas","family":"Busch","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]}],"member":"219","published-online":{"date-parts":[[2018,2,23]]},"reference":[{"key":"S0129054117500290BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"S0129054117500290BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"S0129054117500290BIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102001527"},{"key":"S0129054117500290BIB008","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1990"},{"key":"S0129054117500290BIB009","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"S0129054117500290BIB010","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"S0129054117500290BIB011","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"S0129054117500290BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00227-2"},{"key":"S0129054117500290BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00209-3"},{"key":"S0129054117500290BIB014","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.3.331"},{"key":"S0129054117500290BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/90.532865"},{"key":"S0129054117500290BIB017","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170102"},{"key":"S0129054117500290BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"S0129054117500290BIB021","first-page":"573","volume":"24","author":"Takahashi H.","year":"1980","journal-title":"Math. Japonica"},{"key":"S0129054117500290BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00000-3"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117500290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:39:57Z","timestamp":1565113197000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117500290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11]]},"references-count":15,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2018,2,23]]},"published-print":{"date-parts":[[2017,11]]}},"alternative-id":["10.1142\/S0129054117500290"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117500290","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11]]}}}