{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:16:06Z","timestamp":1725574566754},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540201847"},{"type":"electronic","value":"9783540399896"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39989-6_15","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T21:01:57Z","timestamp":1294434117000},"page":"211-223","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for Oblivious Single-Packet End-to-End Communication"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Adler, M., Fich, F.: The Complexity of End-to-End Communication in Memory-less Networks. In: 18th ACM Symposium on Principles of Distributed Computing (PODC), pp. 239\u2013248 (1999)","DOI":"10.1145\/301308.301364"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1007\/3-540-45022-X_63","volume-title":"Automata, Languages and Programming","author":"M. Adler","year":"2000","unstructured":"Adler, M., Fich, F., Goldberg, L., Paterson, M.: Tight Size Bounds for Packet Headers in Narrow Meshes. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 756\u2013767. Springer, Heidelberg (2000)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Afek, Y., Awerbuch, B., Gaftii, E.: Applying Static Network Protocols to Dynamic Networks. In: 28th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 358\u2013370 (1987)","DOI":"10.1109\/SFCS.1987.7"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Afek, Y., Gafni, E.: End-to-End Communication in Unreliable Networks. In: 7th ACM Symposium on Principles of Distributed Computing (PODC), pp. 131\u2013148 (1988)","DOI":"10.1145\/62546.62570"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Afek, Y., Gafni, E.: Bootstrap Network Resynchonization. In: 10th ACM Symposium on Principles of Distributed Computing (PODC), pp. 295\u2013307 (1991)","DOI":"10.1145\/112600.112625"},{"issue":"6","key":"15_CR6","doi-asserted-by":"publisher","first-page":"1267","DOI":"10.1145\/195613.195651","volume":"41","author":"Y. Afek","year":"1994","unstructured":"Afek, Y., Attiya, H., Fekete, A., Fischer, M., Lynch, N., Mansour, Y., Wang, D.-W., Zuck, L.: Reliable Communication Over Unreliable Channels. Journal of the ACM\u00a041(6), 1267\u20131297 (1994)","journal-title":"Journal of the ACM"},{"issue":"1","key":"15_CR7","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1006\/jagm.1996.0819","volume":"22","author":"Y. Afek","year":"1997","unstructured":"Afek, Y., Awerbuch, B., Gafni, E., Mansour, Y., Ros\u00e9n, A., Shavit, N.: Slide-The Key to Polynomial End-to-End Communication. Journal of Algorithms\u00a022(1), 158\u2013186 (1997)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"15_CR8","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0898-1221(82)90043-8","volume":"8","author":"A. Aho","year":"1982","unstructured":"Aho, A., Ullman, J., Wyler, A., Yannakakis, M.: Bounds on the Size and Transmission Rate of Communication Protocols. Computers and Math with Applications\u00a08(3), 205\u2013214 (1982)","journal-title":"Computers and Math with Applications"},{"key":"15_CR9","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: 17th Conference on Uncertainty in Artificial Intelligence, UAI (2001)"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient Algorithms for Combinatorial Problems on Graphs with Bounded Decomposability-A Survey. BIT\u00a025, 2\u201323 (1985)","journal-title":"BIT"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of Finding Embeddings in a fc-Tree. SIAM J. Alg. Disc. Meth.\u00a08, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/net.3230160405","volume":"16","author":"B. Awerbuch","year":"1986","unstructured":"Awerbuch, B., Even, S.: Reliable Broadcast Protocols in Unreliable Networks. Networks\u00a016, 381\u2013396 (1986)","journal-title":"Networks"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Mansour, Y., Shavit, N.: Polynomial End-to-End Communication. In: 30th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 358\u2013363 (1989)","DOI":"10.1109\/SFCS.1989.63503"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldreich, O., Herzberg, A.: A Quantitative Approach to Dynamic Networks. In: 9th ACM Symposium on Principles of Distributed Computing (PODC), pp. 189\u2013203 (1990)","DOI":"10.1145\/93385.93419"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1145\/362946.362970","volume":"12","author":"K. Bartlett","year":"1969","unstructured":"Bartlett, K., Scantleburg, R., Wilkinson, P.: A Note on Reliable, Full-Duplex Transmission over Half-Duplex Links. Communication of the ACM\u00a012, 260\u2013261 (1969)","journal-title":"Communication of the ACM"},{"key":"15_CR16","first-page":"1","volume":"11","author":"H. Bodlaender","year":"1993","unstructured":"Bodlaender, H.: A Tourist Guide through Treewidth. Acta Cybernetica\u00a011, 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. Bodlaender","year":"1996","unstructured":"Bodlaender, H.: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR18","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Gilbert, J., Hafsteinsson, H., Kloks, T.: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree. Journal of Algorithms\u00a018, 238\u2013255 (1995)","journal-title":"Journal of Algorithms"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Bouchitt\u00e9, V., Kratsch, D., M\u00fcller, H., Todinca, I.: On treewidth approximations. In: 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW (2001)","DOI":"10.1016\/S1571-0653(05)80091-5"},{"key":"15_CR20","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, 2nd edn. Springer, New York (2000)","edition":"2"},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1006\/jctb.1998.1862","volume":"75","author":"R. Diestel","year":"1999","unstructured":"Diestel, R., Jensen, T.R., Gorbunov, K.Y., Thomassen, C.: Highly connected sets and the excluded grid theorem. Journal of Combin. Theory B\u00a075, 61\u201373 (1999)","journal-title":"Journal of Combin. Theory B"},{"issue":"1","key":"15_CR22","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1109\/12.559799","volume":"46","author":"S. Dolev","year":"1997","unstructured":"Dolev, S., Welch, J.: Crash Resilient Communication in Dynamic Networks. IEEE Transactions on Computers\u00a046(1), 14\u201326 (1997)","journal-title":"IEEE Transactions on Computers"},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/BFb0039061","volume-title":"CONCUR \u201990","author":"A. Fekete","year":"1990","unstructured":"Fekete, A., Lynch, N.: The Need for Headers: An Impossibility Result for Communication over Unreliable Channels. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol.\u00a0458, pp. 199\u2013215. Springer, Heidelberg (1990)"},{"issue":"3","key":"15_CR24","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1145\/174147.169676","volume":"40","author":"A. Fekete","year":"1993","unstructured":"Fekete, A., Lynch, N., Mansour, Y., Spinelli, J.: The Impossibility of Implementing Reliable Communication in the Face of Crashes. Journal of the ACM\u00a040(3), 1087\u20131107 (1993)","journal-title":"Journal of the ACM"},{"key":"15_CR25","unstructured":"Fich, F.: End-to-End Communication Protocols. In: 2nd Int. Conference on Principles of Distributed Systems (OPODIS), Hermes, pp. 37\u201343 (1998)"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/3-540-40026-5_24","volume-title":"Distributed Computing","author":"F. Fich","year":"2000","unstructured":"Fich, F., Jakoby, A.: Short Headers Suffice for Communication in a DAG with Link Failures. In: Herlihy, M.P. (ed.) DISC 2000. LNCS, vol.\u00a01914, pp. 360\u2013373. Springer, Heidelberg (2000)"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Herzberg, A., Mansour, Y.: Source to Destination Communication in the Presence of Faults. In: 8th ACM Symposium on Principles of Distributed Computing (PODC), pp. 85\u2013101 (1989)","DOI":"10.1145\/72981.72987"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Herzberg, A.: Connection-Based Communication in Dynamic Networks. In: 11th ACM Symposium on Principles of Distributed Computing (PODC), pp. 13\u201324 (1992)","DOI":"10.1145\/135419.135424"},{"key":"15_CR29","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Ros\u00e9n, A.: Log-Space Polynomial End-to-End Communication. In: 28th ACM Symposium on Theory of Computing (STOC), pp. 559\u2013568 (1995)","DOI":"10.1145\/225058.225273"},{"key":"15_CR30","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jcss.1997.1549","volume":"56","author":"R. Ladner","year":"1998","unstructured":"Ladner, R., LaMarca, A., Tempero, E.: Counting Protocol for Reliable End-to-End Transmission. Journal of Computer and System Sciences\u00a056, 96\u2013111 (1998)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"15_CR31","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/146585.146596","volume":"39","author":"Y. Mansour","year":"1992","unstructured":"Mansour, Y., Schieber, B.: The Intractability of bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels. Journal of the ACM\u00a039(4), 783\u2013799 (1992)","journal-title":"Journal of the ACM"},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"Postel, J.: Internet Protocol. Internet Engineering Task Force Request For Comments 791 (1981)","DOI":"10.17487\/rfc0791"},{"key":"15_CR33","doi-asserted-by":"crossref","unstructured":"Reed, B.: Finding Approximate Separators and Computing Treewidth Quickly. In: 24th ACM Symposium on Theory of Computing (STOC), pp. 221\u2013228 (1992)","DOI":"10.1145\/129712.129734"},{"key":"15_CR34","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. III. Planar Tree-Width. Journal of Combin. Theory B\u00a036, 49\u201364 (1984)","journal-title":"Journal of Combin. Theory B"},{"key":"15_CR35","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. V. Excluding a planar graph. Journal of Combin. Theory B\u00a041, 92\u2013114 (1986)","journal-title":"Journal of Combin. Theory B"},{"key":"15_CR36","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a planar graph. Journal of Combin. Theory B\u00a062, 323\u2013348 (1994)","journal-title":"Journal of Combin. Theory B"},{"issue":"2","key":"15_CR37","first-page":"99","volume":"1","author":"N. Stenning","year":"1976","unstructured":"Stenning, N.: A Data Transfer Protocol. Computer Networks\u00a01(2), 99\u2013110 (1976)","journal-title":"Computer Networks"},{"issue":"5","key":"15_CR38","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1145\/210118.210133","volume":"42","author":"E. Tempero","year":"1995","unstructured":"Tempero, E., Ladner, R.: Recoverable Sequence Transmission Protocols. Journal of the ACM\u00a042(5), 1059\u20131090 (1995)","journal-title":"Journal of the ACM"},{"key":"15_CR39","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1109\/TIT.1983.1056696","volume":"29","author":"U. Vishkin","year":"1983","unstructured":"Vishkin, U.: A Distributed Orientation Algorithm. IEEE Transaction on Information Theory\u00a029, 624\u2013629 (1983)","journal-title":"IEEE Transaction on Information Theory"},{"key":"15_CR40","doi-asserted-by":"crossref","unstructured":"Wang, D.-W., Zuck, L.: Tight Bounds for the Sequence Transmission Problem. In: 8th ACM Symposium on Principles of Distributed Computing (PODC), pp. 73\u201383 (1989)","DOI":"10.1145\/72981.72986"},{"key":"15_CR41","doi-asserted-by":"crossref","unstructured":"Wang, D.-W., Zuck, L.: Real-Time Sequence Transmission Problem. In: 10th ACM Symposium on Principles of Distributed Computing (PODC), pp. 111\u2013124 (1991)","DOI":"10.1145\/112600.112611"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39989-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:03:13Z","timestamp":1559916193000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39989-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540201847","9783540399896"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39989-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}