{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T09:43:13Z","timestamp":1791279793067,"version":"4.1.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319252575","type":"print"},{"value":"9783319252582","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_26","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T03:10:18Z","timestamp":1445224218000},"page":"370-384","source":"Crossref","is-referenced-by-count":14,"title":["Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model"],"prefix":"10.1007","author":[{"given":"Jarkko","family":"Kari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Matamala","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ville","family":"Salo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proc. of the 23rd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2012), pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: Sparsification, spanners, and subgraphs. In: Proc. of PODS 2012, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"26_CR3","unstructured":"Ajtai, M., Koml\u00f3s, J., Simonovits, M., Szemer\u00e9di, E.: The exact solution of the Erdos-T. S\u00f3s conjecture for (large) trees (in preparation)"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-319-12340-0_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Arfaoui","year":"2014","unstructured":"Arfaoui, H., Fraigniaud, P., Ilcinkas, D., Mathieu, F.: Distributedly testing cycle-freeness. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol.\u00a08747, pp. 15\u201328. Springer, Heidelberg (2014)"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Kimmel, P.G.: Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. In: Proc. of the 12th Annual IEEE Conference on Computational Complexity, pp. 239\u2013246 (1997)","DOI":"10.1109\/CCC.1997.612319"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Becker, F., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., Todinca, I.: Adding a referee to an interconnection network: What can (not) be computed in one round. In: Proc. of IPDPS 2011, pp. 508\u2013514 (2011)","DOI":"10.1109\/IPDPS.2011.55"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-319-09620-9_8","volume-title":"Structural Information and Communication Complexity","author":"F. Becker","year":"2014","unstructured":"Becker, F., Montealegre, P., Rapaport, I., Todinca, I.: The simultaneous number-in-hand communication model for networks: Private coins, public coins and determinism. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol.\u00a08576, pp. 83\u201395. Springer, Heidelberg (2014)"},{"issue":"2","key":"26_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"J.A. Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. Journal of Combinatorial Theory, Series B\u00a016(2), 97\u2013105 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proc. of FOCS 2001, pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.jctb.2014.01.001","volume":"106","author":"M. Chudnovsky","year":"2014","unstructured":"Chudnovsky, M., Scott, A., Seymour, P.: Excluding pairs of graphs. Journal of Combinatorial Theory, Series B\u00a0106, 15\u201329 (2014)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"26_CR11","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discrete Applied Mathematics\u00a03(3), 163\u2013174 (1981)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: The communication complexity of distributed task allocation. In: Proc. of PODC 2012, pp. 67\u201376 (2012)","DOI":"10.1145\/2332432.2332443"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proc. of PODC 2014, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"key":"26_CR14","unstructured":"Gronemeier, A.: Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness. In: Proc. of STACS 2009, pp. 505\u2013516 (2009)"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: Proc. of PODS 2015, pp. 241\u2013247 (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"26_CR16","unstructured":"Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. CoRR, abs\/1412.3445 (2014)"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Jayram, T.S.: Hellinger strikes back: A note on the multi-party information complexity of AND. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 562\u2013573. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03685-9_42"},{"issue":"4","key":"26_CR18","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02579141","volume":"4","author":"A.V. Kostochka","year":"1984","unstructured":"Kostochka, A.V.: Lower bound of the hadwiger number of graphs by their average degree. Combinatorica\u00a04(4), 307\u2013316 (1984)","journal-title":"Combinatorica"},{"issue":"1","key":"26_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I. Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Computational Complexity\u00a08(1), 21\u201349 (1999)","journal-title":"Computational Complexity"},{"key":"26_CR20","first-page":"331","volume":"44","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E.: Communication complexity. Adv. Computers\u00a044, 331\u2013360 (1997)","journal-title":"Computers"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. In: Proc. of the 23rd Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2012), pp. 486\u2013501 (2012)","DOI":"10.1137\/1.9781611973099.42"},{"issue":"2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XX: Wagner\u2019s conjecture. Journal of Combinatorial Theory, Series B\u00a092(2), 325\u2013357 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"26_CR23","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D. Seinsche","year":"1974","unstructured":"Seinsche, D.: On a property of the class of n-colorable graphs. Journal of Combinatorial Theory, Series B\u00a016(2), 191\u2013193 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Thomason, A.: An extremal function for contractions of graphs. In: Mathematical Proc. of the Cambridge Philosophical Society, vol.\u00a095, pp. 261\u2013265 (1984)","DOI":"10.1017\/S0305004100061521"},{"issue":"2","key":"26_CR25","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1006\/jctb.2000.2013","volume":"81","author":"A. Thomason","year":"2001","unstructured":"Thomason, A.: The extremal function for complete minors. Journal of Combinatorial Theory, Series B\u00a081(2), 318\u2013338 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"26_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-41527-2_2","volume-title":"Distributed Computing","author":"D.P. Woodruff","year":"2013","unstructured":"Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. In: Afek, Y. (ed.) DISC 2013. LNCS, vol.\u00a08205, pp. 16\u201330. Springer, Heidelberg (2013)"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Yao, A.: Some complexity questions related to distributive computing (preliminary report). In: Proc. of STOC 1979, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25258-2_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T22:17:35Z","timestamp":1748643455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}