{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:02:39Z","timestamp":1725897759088},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_42","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"498-509","source":"Crossref","is-referenced-by-count":4,"title":["Constant-Time Algorithms for Sparsity Matroids"],"prefix":"10.1007","author":[{"given":"Hiro","family":"Ito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shin-Ichi","family":"Tanigawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"42_CR1","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM Comp.\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM Comp."},{"key":"42_CR2","volume-title":"Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Reprint edition","author":"E. Demaine","year":"2008","unstructured":"Demaine, E., O\u2019Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Reprint edition. Cambridge University Press, New York (2008)"},{"key":"42_CR3","unstructured":"Edmonds, J.: Edge disjoint branchings. In: Rustin, B. (ed.) Combinatorial Algorithms, pp. 91\u201396. Algorithmics Press (1973)"},{"issue":"3","key":"42_CR4","first-page":"251","volume":"28","author":"A. Frank","year":"1980","unstructured":"Frank, A.: On the orientation of graphs. J.\u00a0Comb.\u00a0Theory,\u00a0B\u00a028(3), 251\u2013261 (1980)","journal-title":"J.\u00a0Comb.\u00a0Theory,\u00a0B"},{"key":"42_CR5","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press (2011)"},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/S0166-218X(02)00460-2","volume":"131","author":"A. Frank","year":"2003","unstructured":"Frank, A., Kir\u00e1ly, T.: Combined connectivity augmentation and orientation problems. Discrete Appl. Math.\u00a0131, 401\u2013419 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"42_CR7","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF01758774","volume":"7","author":"H. Gabow","year":"1992","unstructured":"Gabow, H., Westermann, H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica\u00a07(1), 465\u2013497 (1992)","journal-title":"Algorithmica"},{"key":"42_CR8","unstructured":"Goldreich, O.: Intriduction to testing graph properties. Technical report. Electronic Colloquium on Computational Complexity, ECCC (2010)"},{"issue":"2","key":"42_CR9","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O. Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica\u00a032(2), 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"42_CR10","first-page":"129","volume":"63","author":"R. Haas","year":"2002","unstructured":"Haas, R.: Characterizations of arboricity of graphs. Ars Comb.\u00a063, 129\u2013138 (2002)","journal-title":"Ars Comb."},{"issue":"3","key":"42_CR11","doi-asserted-by":"crossref","first-page":"186","DOI":"10.15807\/jorsj.26.186","volume":"26","author":"H. Imai","year":"1983","unstructured":"Imai, H.: Network flow algorithms for lower truncated transversal polymatroids. Journal of the Operations Research Society of Japan\u00a026(3), 186\u2013210 (1983)","journal-title":"Journal of the Operations Research Society of Japan"},{"issue":"6","key":"42_CR12","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1137\/S0097539703436424","volume":"33","author":"T. Kaufman","year":"2004","unstructured":"Kaufman, T., Krivelevich, M., Ron, D.: Tight bounds for testing bipartiteness in general graphs. SIAM Journal on Computing\u00a033(6), 1441\u20131483 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"42_CR13","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01534980","volume":"4","author":"G. Laman","year":"1970","unstructured":"Laman, G.: On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics\u00a04(4), 331\u2013340 (1970)","journal-title":"Journal of Engineering Mathematics"},{"issue":"8","key":"42_CR14","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.1016\/j.disc.2007.07.104","volume":"308","author":"A. Lee","year":"2008","unstructured":"Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discrete Mathematics\u00a0308(8), 1425\u20131437 (2008)","journal-title":"Discrete Mathematics"},{"key":"42_CR15","doi-asserted-by":"publisher","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"C. Nash-Williams","year":"1960","unstructured":"Nash-Williams, C.: On orientations, connectivity and odd vertex pairings in finite graphs. Canad. J. Math.\u00a012, 555\u2013567 (1960)","journal-title":"Canad. J. Math."},{"issue":"1","key":"42_CR16","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"1","author":"C. Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.: Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society\u00a01(1), 445\u2013450 (1961)","journal-title":"Journal of the London Mathematical Society"},{"issue":"1","key":"42_CR17","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"1","author":"C. Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.: Decomposition of finite graphs into forests. Journal of the London Mathematical Society\u00a01(1), 12 (1964)","journal-title":"Journal of the London Mathematical Society"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proc. of FOCS 2008, pp. 327\u2013336 (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Newman, I., Sohler, C.: Every property of hyperfinite graphs is testable. In: Proc. of STOC 2011, pp. 675\u2013684 (2011)","DOI":"10.1145\/1993636.1993726"},{"key":"42_CR20","unstructured":"Orenstein, Y.: Property testing in directed graphs. Master\u2019s thesis, Tel-Aviv University (2010)"},{"key":"42_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"36","author":"W.T. Tutte","year":"1961","unstructured":"Tutte, W.T.: On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society\u00a036, 221\u2013230 (1961)","journal-title":"Journal of the London Mathematical Society"},{"issue":"2","key":"42_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1137\/0401025","volume":"1","author":"W. Whiteley","year":"1988","unstructured":"Whiteley, W.: The union of matroids and the rigidity of frameworks. SIAM Journal on Discrete Mathematics\u00a01(2), 237\u2013255 (1988)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"42_CR23","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1090\/conm\/197\/02540","volume":"197","author":"W. Whiteley","year":"1996","unstructured":"Whiteley, W.: Some matroids from discrete applied geometry. Contemporary Mathematics\u00a0197, 171\u2013312 (1996)","journal-title":"Contemporary Mathematics"},{"issue":"3","key":"42_CR24","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/s00453-010-9477-y","volume":"62","author":"Y. Yoshida","year":"2012","unstructured":"Yoshida, Y., Ito, H.: Property testing on k-vertex-connectivity of graphs. Algorithmica\u00a062(3), 701\u2013712 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"42_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s11424-010-9280-5","volume":"23","author":"Y. Yoshida","year":"2010","unstructured":"Yoshida, Y., Ito, H.: Testing k-edge-connectivity of digraphs. Journal of System Science and Complexity\u00a023(1), 91\u2013101 (2010)","journal-title":"Journal of System Science and Complexity"},{"key":"42_CR26","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: An improved constant-time approximation algorithm for maximum\u00a0matchings. In: Proc.\u00a0of STOC 2009, pp. 225\u2013234 (2009)","DOI":"10.1145\/1536414.1536447"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31594-7_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:15:04Z","timestamp":1620130504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}