{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:11:37Z","timestamp":1725455497087},"publisher-location":"Berlin\/Heidelberg","reference-count":6,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016276","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T00:39:17Z","timestamp":1131842357000},"page":"501-511","source":"Crossref","is-referenced-by-count":1,"title":["Near optimal algorithms for finding minimum Steiner trees on random graphs"],"prefix":"10.1007","author":[{"given":"L.","family":"Kucera","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Protasi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Talamo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"47_CR1","unstructured":"Erdos, P., A. Renyi: \"On random graphs 1\", Publications Mathematicae (Debrecem), Vol. 6 (1959)."},{"key":"47_CR2","volume-title":"Graph algorithms","author":"S. Even","year":"1979","unstructured":"Even, S.: \"Graph algorithms\", Computer Science Press, Potomac (1979)."},{"key":"47_CR3","doi-asserted-by":"crossref","unstructured":"Foulds, L.R., V.J. Rayward-Smith: \"Steiner problems in graphs: algorithms and applications\", Engineering Optimization, 7 (1983).","DOI":"10.1080\/03052158308960625"},{"key":"47_CR4","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: \"Reducibility among Combinatorial Problems\", in Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher, New York, Plenum Press (1972)."},{"key":"47_CR5","doi-asserted-by":"crossref","unstructured":"Kou, L., G. Markowsky, L. Berman: \"A Fast Algorithm for Steiner Trees\", Acta Informatica, 15 (1981).","DOI":"10.1007\/BF00288961"},{"key":"47_CR6","unstructured":"Wu, Y.F., P. Widmayer, C.K. Wong: \"A Faster Approximation Algorithm for the Steiner problem in graphs\", IBM Thomas Watson Research Center Report (1984)."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016276.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:35:56Z","timestamp":1607531756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":6,"URL":"https:\/\/doi.org\/10.1007\/bfb0016276","relation":{},"subject":[]}}