{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:29Z","timestamp":1740122429041,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T00:00:00Z","timestamp":1669593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T00:00:00Z","timestamp":1669593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100006115","name":"Institute for Research in Fundamental Sciences","doi-asserted-by":"publisher","award":["98050014"],"award-info":[{"award-number":["98050014"]}],"id":[{"id":"10.13039\/501100006115","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10878-022-00929-z","type":"journal-article","created":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T04:31:39Z","timestamp":1669609899000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An estimator for matching size in low arboricity graphs with two applications"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9032-9958","authenticated-orcid":false,"given":"Hossein","family":"Jowhari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,28]]},"reference":[{"issue":"1","key":"929_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1999","unstructured":"Alon N, Matias Y, Szegedy M (1999) The space complexity of approximating the frequency moments. J Comput Syst Sci 58(1):137\u2013147","journal-title":"J Comput Syst Sci"},{"key":"929_CR2","unstructured":"Bernstein A (2020) Improved bounds for matching in random-order streams. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference) (Artur Czumaj, Anuj Dawar, and Emanuela Merelli, eds.), LIPIcs, vol 168, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 12:1\u201312:13"},{"issue":"1","key":"929_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s00453-018-0449-y","volume":"81","author":"M Bury","year":"2019","unstructured":"Bury M, Grigorescu E, McGregor A, Monemizadeh M, Schwiegelshohn C, Vorotnikova S, Zhou S (2019) Structural results on matching estimation with applications to streaming. Algorithmica 81(1):367\u2013392","journal-title":"Algorithmica"},{"key":"929_CR4","doi-asserted-by":"crossref","unstructured":"Behnezhad S, Hajiaghayi MT, Harris DG (2019) Exponentially faster massively parallel maximal matching. In: 60th IEEE annual symposium on foundations of computer science, FOCS 2019, Baltimore, Maryland, USA, November 9\u201312, 2019 (David Zuckerman, ed.), IEEE Computer Society, pp 1637\u20131649","DOI":"10.1109\/FOCS.2019.00096"},{"key":"929_CR5","doi-asserted-by":"crossref","unstructured":"Chitnis R, Cormode G, Esfandiari H, Hajiaghayi MT, McGregor A, Monemizadeh M, Vorotnikova S (2016) Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 (Robert Krauthgamer, ed.), SIAM, pp 1326\u20131344","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"929_CR6","doi-asserted-by":"crossref","unstructured":"Chitnis RH, Cormode G, Hajiaghayi MT, Monemizadeh M (2015) Parameterized streaming: maximal matching and vertex cover. In: Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015 (Piotr Indyk, ed.), SIAM, pp 1234\u20131251","DOI":"10.1137\/1.9781611973730.82"},{"key":"929_CR7","doi-asserted-by":"crossref","unstructured":"Czygrinow A, Hanckowiak M, Szymanska E (2009) Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs, Algorithms and Computation. IN: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings (Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, eds.), Lecture Notes in Computer Science, vol 5878, Springer, pp 668\u2013678","DOI":"10.1007\/978-3-642-10631-6_68"},{"key":"929_CR8","unstructured":"Cormode G, Jowhari H, Monemizadeh M, Muthukrishnan S (2017) The sparse awakens: streaming algorithms for matching size estimation in sparse graphs. In: 25th Annual European symposium on algorithms, ESA 2017, September 4\u20136, 2017, Vienna, Austria, pp 29:1\u201329:15"},{"key":"929_CR9","doi-asserted-by":"crossref","unstructured":"Esfandiari H, Hajiaghayi MT, Liaghat V, Monemizadeh M, Onak K (2015) Streaming algorithms for estimating the matching size in planar graphs and beyond. In: Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015 (Piotr Indyk, ed.), SIAM, pp 1217\u20131233","DOI":"10.1137\/1.9781611973730.81"},{"key":"929_CR10","doi-asserted-by":"crossref","unstructured":"Esfandiari H, Hajiaghayi MT, Monemizadeh M (2016) Finding large matchings in semi-streaming. In: IEEE international conference on data mining workshops, ICDM Workshops 2016, December 12-15, 2016, Barcelona, Spain (Carlotta Domeniconi, Francesco Gullo, Francesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, and Xindong Wu, eds.), IEEE Computer Society, pp 608\u2013614","DOI":"10.1109\/ICDMW.2016.0092"},{"key":"929_CR11","unstructured":"Ghaffari M, Grunau C, Jin C (2020) Improved MPC algorithms for mis, matching, and coloring on trees and beyond. IN: 34th International symposium on distributed computing, DISC 2020, October 12-16, 2020, Virtual Conference (Hagit Attiya, ed.), LIPIcs, vol 179, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 34:1\u201334:18"},{"key":"929_CR12","unstructured":"Ghaffari M, Wajc D (2019) Simplified and space-optimal semi-streaming (2+epsilon)-approximate matching. In: 2nd Symposium on simplicity in algorithms, SOSA 2019, January 8\u20139, 2019, San Diego, CA, USA (Jeremy T. Fineman and Michael Mitzenmacher, eds.), OASICS, vol 69, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 13:1\u201313:8"},{"key":"929_CR13","doi-asserted-by":"crossref","unstructured":"Kapralov M, Khanna S, Sudan M (2014) Approximating matching size from random streams. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014 (Chandra Chekuri, ed.), SIAM, pp 734\u2013751","DOI":"10.1137\/1.9781611973402.55"},{"key":"929_CR14","doi-asserted-by":"crossref","unstructured":"Kapralov M, Mitrovic S, Norouzi-Fard A, Tardos J (2020) Space efficient approximation to maximum matching size from uniform edge samples. In: Proceedings of the 2020 ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020 (Shuchi Chawla, ed.), SIAM, pp 1753\u20131772","DOI":"10.1137\/1.9781611975994.107"},{"issue":"5","key":"929_CR15","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/2786753","volume":"62","author":"Z Lotker","year":"2015","unstructured":"Lotker Z, Patt-Shamir B, Pettie S (2015) Improved distributed approximate matching. J ACM 62(5):38:1-38:17","journal-title":"J ACM"},{"key":"929_CR16","unstructured":"McGregor A (2005) Finding graph matchings in data streams, Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques. In: 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th international workshop on randomization and computation, RANDOM 2005, Berkeley, CA, USA, August 22\u201324, 2005, Proceedings (Chandra Chekuri, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Luca Trevisan, eds.), Lecture Notes in Computer Science. Springer, vol 3624, pp 170\u2013181"},{"key":"929_CR17","unstructured":"McGregor A, Vorotnikova S (2016) Planar matching in streams revisited, Proceedings of the 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)"},{"key":"929_CR18","unstructured":"McGregor A, Vorotnikova S (2018) A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs, SOSA, pp 14:1\u201314:4"},{"key":"929_CR19","doi-asserted-by":"crossref","unstructured":"Nash-Williams C (1964) Decomposition of finite graphs into forests. J Lond Math Soc 39(12)","DOI":"10.1112\/jlms\/s1-39.1.12"},{"issue":"1","key":"929_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/3147.3165","volume":"11","author":"JS Vitter","year":"1985","unstructured":"Vitter JS (1985) Random sampling with a reservoir. ACM Trans Math Softw 11(1):37\u201357","journal-title":"ACM Trans Math Softw"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00929-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00929-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00929-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:47:47Z","timestamp":1675496867000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00929-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,28]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["929"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00929-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,11,28]]},"assertion":[{"value":"30 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"21"}}