{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T21:30:18Z","timestamp":1781559018502,"version":"3.54.5"},"reference-count":19,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7894,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider Steiner tree problems and connected dominating set problems for several classes of graphs. We give a polynomial algorithm and a min\u2010max theorem for the cardinality Steiner problem in strongly chordal graphs and a polynomial algorithm for the weighted connected dominating set problem in series\u2010parallel graphs. We establish simple direct transformations between Steiner problems and connected domination problems for several classes of graphs and establish related <jats:italic>NP<\/jats:italic>\u2010completeness results.<\/jats:p>","DOI":"10.1002\/net.3230150109","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T19:18:12Z","timestamp":1178911092000},"page":"109-124","source":"Crossref","is-referenced-by-count":97,"title":["Steiner trees, connected domination and strongly chordal graphs"],"prefix":"10.1002","volume":"15","author":[{"given":"Kevin","family":"White","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Farber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Pulleyblank","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90028-2"},{"key":"e_1_2_1_3_2","unstructured":"G.Cornu\u00e9jols J.FonluptandD.Naddef The graphical travelling salesman problem and some related integer polyhedra. Research Report no. 378 Laboratoire d'Informatique et de Math\u00e9matiques Appliqu\u00e9es de Grenoble (1983)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(65)90125-3"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90154-1"},{"key":"e_1_2_1_7_2","unstructured":"M.Farber andR. E.Jamison Convexity in graphs and hypergraphs. Research Report CORR 83\u201046 University of Waterloo (1983)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_9_2","volume-title":"Computers and Intractibility","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_10_2","unstructured":"A. J.Hoffman A. W. J.KolenandM.Sakarovitch Totally\u2010balanced and greedy matrices(in press)."},{"key":"e_1_2_1_11_2","first-page":"85","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","year":"1962"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90003-3"},{"key":"e_1_2_1_13_2","unstructured":"E.Korach On dual integrality min\u2010max equalities and algorithms in combinatorial linear programs. Ph. D. thesis University of Waterloo (1982)."},{"key":"e_1_2_1_14_2","unstructured":"R.Laskar andJ.Pfaff Domination and irredundance in split graphs. Technical Report 430 Clemson University (1983)."},{"key":"e_1_2_1_15_2","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"e_1_2_1_16_2","unstructured":"J.Pfaff R.LaskarandS. T.Hedetniemi NP\u2010completeness of total and connected domination and irredundance for bipartite graphs. Technical Report 428 Clempon University (1983)."},{"key":"e_1_2_1_17_2","series-title":"Industrial and Systems Engineering Report Series J\u201082\u20105","volume-title":"A polynomial algorithm for a class of Steiner tree problems on graphs","author":"Rardin R. L.","year":"1982"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130202"},{"key":"e_1_2_1_20_2","unstructured":"K.White Steiner trees and strongly chordal graphs. M. Math thesis University of Waterloo (1983)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150109","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150109","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T15:45:14Z","timestamp":1697816714000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,3]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,3]]}},"alternative-id":["10.1002\/net.3230150109"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150109","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,3]]}}}