{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:23:47Z","timestamp":1759638227203,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319292205"},{"type":"electronic","value":"9783319292212"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-29221-2_27","type":"book-chapter","created":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T12:02:54Z","timestamp":1455278574000},"page":"308-325","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Steiner Tree in Split Graphs - Dichotomy Results"],"prefix":"10.1007","author":[{"given":"Madhu","family":"Illuri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Renjith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Sadagopan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"27_CR1","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing steiner minimal trees. SIAM J. Appl. Math. 32(4), 835\u2013859 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"27_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/net.3230150109","volume":"15","author":"K White","year":"1985","unstructured":"White, K., Farber, M., Pulleyblank, W.: Steiner trees, connected domination and strongly chordal graphs. Networks 15(1), 109\u2013124 (1985)","journal-title":"Networks"},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/978-0-387-30165-5_18","volume-title":"Handbook of Optimization in Telecommunications","author":"S Vo","year":"2006","unstructured":"Vo, S.: Steiner tree problems in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 459\u2013492. Springer, Heidelberg (2006)"},{"key":"27_CR4","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"27_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"27_CR6","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(86)90135-3","volume":"23","author":"AA Bertossi","year":"1986","unstructured":"Bertossi, A.A., Bonuccelli, M.A.: Hamiltonian circuits in interval graph generalizations. Inf. Process. Lett. 23, 195\u2013200 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"27_CR8","doi-asserted-by":"publisher","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(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"27_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0304-3975(87)90067-3","volume":"53","author":"H Muller","year":"1987","unstructured":"Muller, H., Brandstadt, A.: The NP-completeness of steiner tree and dominating set for chordal bipartite graphs. Theoret. Comput. Sci. 53(2), 257\u2013265 (1987)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"27_CR10","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"JM Keil","year":"1985","unstructured":"Keil, J.M.: Finding hamiltonian circuits in interval graphs. Inf. Process. Lett. 20(4), 201\u2013206 (1985)","journal-title":"Inf. Process. Lett."},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1016\/j.aml.2010.11.030","volume":"24","author":"RW Hung","year":"2011","unstructured":"Hung, R.W., Chang, M.S.: Linear-time certifying algorithms for the path cover and hamiltonian cycle problems on interval graphs. Appl. Math. Lett. 24, 648\u2013652 (2011)","journal-title":"Appl. Math. Lett."},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"BS Panda","year":"2003","unstructured":"Panda, B.S., Das, S.K.: A linear time recognition algorithm for proper interval graphs. Inf. Process. Lett. 87, 153\u2013161 (2003)","journal-title":"Inf. Process. Lett."},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1016\/j.ipl.2009.07.010","volume":"109","author":"L Ibarra","year":"2009","unstructured":"Ibarra, L.: A simple algorithm to find hamiltonian cycles in proper interval graphs. Inf. Process. Lett. 109, 1105\u20131108 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"27_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"JA Wald","year":"1983","unstructured":"Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13(2), 159\u2013167 (1983)","journal-title":"Networks"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The steiner problem in graphs. Networks 1, 195\u2013207 (1972)","journal-title":"Networks"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"issue":"3","key":"27_CR18","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00407-013-0127-z","volume":"68","author":"M Brazil","year":"2014","unstructured":"Brazil, M., Graham, R.L., Thomas, D.A., Zachariasen, M.: On the history of the euclidean steiner tree problem. Arch. Hist. Exact Sci. 68(3), 327\u2013354 (2014)","journal-title":"Arch. Hist. Exact Sci."},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/978-3-642-40450-4_57","volume-title":"Algorithms \u2013 ESA 2013","author":"M Jones","year":"2013","unstructured":"Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Such\u00fd, O.: Parameterized complexity of directed steiner tree on sparse graphs. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 671\u2013682. Springer, Heidelberg (2013)"},{"key":"27_CR20","unstructured":"Zosin, L., Khuller, S.: On directed steiner trees. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 59\u201363 (2002)"},{"key":"27_CR21","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2003","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Pearson Education, New Delhi (2003)","edition":"2"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An \n                    \n                      \n                    \n                    $${O}(\\sqrt{V}{E})$$\n                   algorithm for finding maximum matching in general graphs. In: IEEE Annual Symposium on Foundations of Computer Science (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"27_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of the Symposium on the Complexity of Computer Computations, pp. 85\u2013103 (1972)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29221-2_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T10:12:37Z","timestamp":1559383957000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29221-2_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319292205","9783319292212"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29221-2_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}