{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T19:25:32Z","timestamp":1649186732581},"reference-count":34,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1999,5,1]],"date-time":"1999-05-01T00:00:00Z","timestamp":925516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5191,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Mathematics"],"published-print":{"date-parts":[[1999,5]]},"DOI":"10.1016\/s0012-365x(99)00012-6","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T12:12:16Z","timestamp":1027599136000},"page":"133-159","source":"Crossref","is-referenced-by-count":1,"title":["Edge-disjoint spanners of complete graphs and complete digraphs"],"prefix":"10.1016","volume":"203","author":[{"given":"Christian","family":"Laforest","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arthur L.","family":"Liestman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas C.","family":"Shermer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Sotteau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0012-365X(99)00012-6_BIB1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","article-title":"On sparse spanners of weighted graphs","volume":"9","author":"Alth\u00f6fer","year":"1993","journal-title":"Discrete Comput. Geom."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB2","unstructured":"B. Awerbuch, A. Baratz, D. Peleg, Efficient broadcast and light-weight spanners, Technical Report CS92-22, the Weizmann Institute of Science, Rehovot, Israel, 1992."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB3","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1137\/S0097539794271898","article-title":"Near-linear time construction of sparse neighborhood covers","volume":"28","author":"Awerbuch","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, D. Peleg, Sparse partitions, 31st IEEE Symposium on Foundations of Computer Science, 1990, pp. 503\u2013513.","DOI":"10.1109\/FSCS.1990.89571"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB5","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s, Extremal Graph Theory, Academic Press, London, 1978, p. 216.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0095-8956(74)90095-1","article-title":"Disjoint factors of diameter two in complete graphs","volume":"16","author":"Bos\u00e1k","year":"1974","journal-title":"J. Combin. Theory, Ser. B"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB7","unstructured":"J. Bos\u00e1k, A. Rosa, \u0160. Zn\u00e1m, On decompositions of complete graphs into factors with given diameters, in: P. Erd\u00f6s, G. Katona (Eds.), Theory of Graphs, Proceedings of Colloq. Tihany, 1966, Academic Press, New York and Academy Kiad\u00f3, Budapest, 1968, pp. 37\u201356."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB8","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0166-218X(94)90073-6","article-title":"NP-completeness of minimum spanner problems","volume":"48","author":"Cai","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB9","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/BF01293665","article-title":"Isomorphic tree spanner problems","volume":"14","author":"Cai","year":"1995","journal-title":"Algorithmica"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB10","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S0895480192237403","article-title":"Tree spanners","volume":"8","author":"Cai","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB11","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1002\/net.3230240406","article-title":"Spanners in graphs of bounded degree","volume":"24","author":"Cai","year":"1994","journal-title":"Networks"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB12","doi-asserted-by":"crossref","unstructured":"B. Chandra, G. Das, G. Narasimhan, J. Soares, New sparseness results on graph spanners, Proceedings of eighth ACM Symposium on Computational Geometry, 1992.","DOI":"10.1145\/142675.142717"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB13","doi-asserted-by":"crossref","unstructured":"E. Cohen, Fast algorithms for constructing t-spanners and paths with stretch t, Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 648\u2013658.","DOI":"10.1109\/SFCS.1993.366822"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB14","doi-asserted-by":"crossref","unstructured":"D. Dor, S. Halperin, U. Zwick, All pairs almost shortest paths, Proceedings of 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 452\u2013461.","DOI":"10.1109\/SFCS.1996.548504"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB15","first-page":"767","article-title":"The diameter of a strongly connected graph (in Russian)","volume":"170","author":"Goldberg","year":"1966","journal-title":"Dokl. AN SSR"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB16","doi-asserted-by":"crossref","unstructured":"R. Harbane, C. Padro, Spanners of underlying graphs of iterated line digraphs, Proceedings of third Colloqium on Structural Information & Communication Complexity, Carleton Univ. Press, 1996.","DOI":"10.1016\/S0020-0190(97)00074-4"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB17","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1137\/S0895480194266628","article-title":"Spanners of hypercube-derived networks","volume":"9","author":"Heydemann","year":"1966","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB18","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1006\/jagm.1994.1032","article-title":"Generating sparse 2-spanners","volume":"17","author":"Kortsarz","year":"1994","journal-title":"J. Algorithms"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB19","doi-asserted-by":"crossref","first-page":"1438","DOI":"10.1137\/S0097539794268753","article-title":"Generating low-degree 2-spanners","volume":"27","author":"Kortsarz","year":"1998","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB20","doi-asserted-by":"crossref","unstructured":"C. Laforest, A.L. Liestman, T.C. Shermer, D. Sotteau, Edge disjoint graph spanners of complete graphs and complete digraphs (extended abstract), Proceedings of 30th Hawaii International Conference on System Sciences, vol. I, 1997, pp. 191\u2013199.","DOI":"10.1109\/HICSS.1997.667214"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB21","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1142\/S0129626491000197","article-title":"Additive spanners for hypercubes","volume":"1","author":"Liestman","year":"1991","journal-title":"Par. Proc. Lett."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB22","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/net.3230230206","article-title":"Grid spanners","volume":"23","author":"Liestman","year":"1993","journal-title":"Networks"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB23","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/net.3230230417","article-title":"Additive graph spanners","volume":"23","author":"Liestman","year":"1993","journal-title":"Networks"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB24","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0895480193251635","article-title":"Degree-constrained network spanners with non-constant delay","volume":"8","author":"Liestman","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB25","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0166-218X(95)00050-2","article-title":"Degree-constrained spanners for multi-dimensional grids","volume":"68","author":"Liestman","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB26","unstructured":"D.E. Lucas, R\u00e9cr\u00e9ations Math\u00e9matiques, vol. II, Gauthier Villars, Paris, 1892."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB27","unstructured":"Y. Mansour, D. Peleg, An approximation algorithm for minimum-cost network design, Technical Report CS94-22, the Weizmann Institute of Science, 1994."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB28","unstructured":"I. Niven, H.S. Zuckerman, An Introduction to the Theory of Numbers, fourth ed., Wiley, New York, 1980, p. 42."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","article-title":"Graph spanners","volume":"13","author":"Peleg","year":"1989","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB30","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/0218050","article-title":"An optimal synchronizer for the hypercube","volume":"18","author":"Peleg","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jpdc.1995.1024","article-title":"Degree-constrained pyramid spanners","volume":"25","author":"Richards","year":"1995","journal-title":"J. Partial Distr. Comput."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB32","first-page":"147","article-title":"The nonexistence of a decomposition of complete graph K12 into three factors with diameter two","volume":"21","author":"Stacho","year":"1996","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"10.1016\/S0012-365X(99)00012-6_BIB33","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0095-8956(80)90044-1","article-title":"A Hamiltonian decomposition of K2n*, 2n \u2a7e 8","volume":"29","author":"Tillson","year":"1980","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0012-365X(99)00012-6_BIB34","first-page":"257","article-title":"On the decomposition of the complete directed graph into factors with given diameters","volume":"20","author":"Tomov\u00e1","year":"1970","journal-title":"Mat. \u010cas."}],"container-title":["Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0012365X99000126?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0012365X99000126?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T10:04:42Z","timestamp":1578477882000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0012365X99000126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,5]]},"references-count":34,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1999,5]]}},"alternative-id":["S0012365X99000126"],"URL":"https:\/\/doi.org\/10.1016\/s0012-365x(99)00012-6","relation":{},"ISSN":["0012-365X"],"issn-type":[{"value":"0012-365X","type":"print"}],"subject":[],"published":{"date-parts":[[1999,5]]}}}