{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:24:02Z","timestamp":1710339842087},"reference-count":21,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,7,24]],"date-time":"2007-07-24T00:00:00Z","timestamp":1185235200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A spanning tree <jats:italic>T<\/jats:italic> of a graph <jats:italic>G<\/jats:italic> is said to be a tree <jats:italic>t<\/jats:italic>\u2010spanner if the distance between any two vertices in <jats:italic>T<\/jats:italic> is at most <jats:italic>t<\/jats:italic> times their distance in <jats:italic>G<\/jats:italic>. While the complexity of the problem of recognizing whether a graph has a tree <jats:italic>t<\/jats:italic>\u2010spanner is known for any fixed <jats:italic>t<\/jats:italic>\u22603, the case <jats:italic>t<\/jats:italic> = 3 is still open. H.\u2010O. Le and V. B. Le (1999, Networks, 34(2), 81\u201087) have shown that every directed path graph admits a tree 3\u2010spanner by proposing an algorithm to construct a tree 3\u2010spanner of a given directed path graph. In this paper, we point out a flaw in their algorithm by producing a directed path graph for which their algorithm fails to produce a tree 3\u2010spanner although the graph admits a tree 3\u2010spanner. Furthermore, we show that directed path graphs need not admit tree 3\u2010spanners in general. Next, we show that directed path graphs of diameter two always admit tree 2\u2010spanners and hence tree 3\u2010spanners. Finally, we show that a tree 2\u2010spanner of a diameter two directed path graph can be constructed in linear time. \u00a9 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 203\u2013210 2007<\/jats:p>","DOI":"10.1002\/net.20198","type":"journal-article","created":{"date-parts":[[2007,7,24]],"date-time":"2007-07-24T20:16:35Z","timestamp":1185308195000},"page":"203-210","source":"Crossref","is-referenced-by-count":3,"title":["On tree 3\u2010spanners in directed path graphs"],"prefix":"10.1002","volume":"50","author":[{"given":"B.S.","family":"Panda","sequence":"first","affiliation":[]},{"given":"Anita","family":"Das","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,7,24]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189308"},{"key":"e_1_2_1_3_2","article-title":"Efficient broadcast and light\u2010weighted spanners","author":"Awerbuch B.","year":"1992","journal-title":"Manuscript"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90038-2"},{"key":"e_1_2_1_5_2","unstructured":"1986 Toronto S. Bhatt F. Chung F. Leighton A. Rosenberg Optimal simulation of tree machines 274 282"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0962"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00424-9"},{"key":"e_1_2_1_8_2","unstructured":"L.Cai Tree spanners: Spanning trees that approximate the distances University of Toronto 1992."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192237403"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992776"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00226-2"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90021-7"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<81::AID-NET1>3.0.CO;2-P"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00078-6"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90042-0"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2001"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00163-9"},{"key":"e_1_2_1_18_2","volume-title":"SIAM monograph on discrete mathematics and applications","author":"Peleg D.","year":"2000"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_20_2","unstructured":"1987 Vancouver D. Peleg J. D. Ullman An optimal synchronizer for the hypercube 77 85"},{"key":"e_1_2_1_21_2","first-page":"411","volume-title":"Molecular systematics","author":"Swofford D. L.","year":"1990"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2641"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20198","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T05:53:09Z","timestamp":1697608389000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,24]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1002\/net.20198"],"URL":"https:\/\/doi.org\/10.1002\/net.20198","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,24]]}}}