{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:26:13Z","timestamp":1761611173062},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_46","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"561-570","source":"Crossref","is-referenced-by-count":21,"title":["A Faster Algorithm for the Steiner Tree Problem"],"prefix":"10.1007","author":[{"given":"Daniel","family":"M\u00f6lle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Richter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"46_CR1","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: SODA10th, pp. 856\u2013857 (1999)"},{"key":"46_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. IPL\u00a032, 171\u2013176 (1989)","journal-title":"IPL"},{"key":"46_CR3","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks\u00a01, 195\u2013207 (1972)","journal-title":"Networks"},{"key":"46_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"F.V. Fomin","year":"2005","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: Domination \u2013 A case study. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, Springer, Heidelberg (2005)"},{"key":"46_CR5","unstructured":"Iwama, K., Tamaki, S.: Improved upper bounds for 3-SAT. In: SODA15th, pp. 328\u2013328 (2004)"},{"key":"46_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_34","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Kneis","year":"2005","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Algorithm based on the treewidth of sparse graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, Springer, Heidelberg (2005)"},{"key":"46_CR7","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: SODA11th, pp. 770\u2013779 (2000)"},{"key":"46_CR8","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. Journal of Algorithms\u00a07, 425\u2013440 (1986)","journal-title":"Journal of Algorithms"},{"key":"46_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-540-45198-3_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Scott","year":"2003","unstructured":"Scott, A., Sorkin, G.B.: Faster algorithms for Max-CUT and Max-CSP, with polynomial expected time for sparse instances. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 382\u2013395. Springer, Heidelberg (2003)"},{"key":"46_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T03:31:13Z","timestamp":1552361473000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/11672142_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}