{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:34Z","timestamp":1787340334306,"version":"build-2736575974"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We present a new algebraic formulation for computing edge connectivities in a directed graph, using ideas developed in network coding. This reduces the problem of computing edge connectivities to solving systems of linear equations, thus allowing us to use tools in linear algebra to design new algorithms. Using the algebraic formulation, we obtain faster algorithms for computing single source edge connectivities and all pairs edge connectivities. In some settings, the amortized time to compute the edge connectivity for one pair is sublinear. Through this connection, we have also found an interesting use of expanders and superconcentrators to design fast algorithms for some graph connectivity problems.<\/jats:p>","DOI":"10.1137\/110844970","type":"journal-article","created":{"date-parts":[[2013,5,2]],"date-time":"2013-05-02T18:12:15Z","timestamp":1367518335000},"page":"733-751","source":"Crossref","is-referenced-by-count":11,"title":["Graph Connectivities, Network Coding, and Expander Graphs"],"prefix":"10.1137","volume":"42","author":[{"given":"Ho Yee","family":"Cheung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai Man","family":"Leung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,5,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"atypb3","first-page":"225","author":"Alon N.","year":"2010","journal-title":"NJ"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142993226983"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1093"},{"key":"atypb6","first-page":"605","author":"Bhalgat A.","year":"2007","journal-title":"New York"},{"key":"atypb7","first-page":"455","author":"Bhalgat A.","year":"2008","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010029"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793256223"},{"key":"atypb10","first-page":"549","author":"Cheung H. Y.","year":"2012","journal-title":"New York"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"E. Erez and M. Feder,\n                      Convolutional network codes\n                      , in Proceedings of the IEEE International Symposium on Information Theory, IEEE Press, Piscataway, NJ, 2004, p. 146.","DOI":"10.1109\/ISIT.2004.1365183"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"atypb14","first-page":"696","author":"Gabow H. N.","year":"1994","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"atypb16","first-page":"32","author":"Goldberg A.V.","year":"1997","journal-title":"NJ"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/070684008"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881746"},{"key":"atypb19","first-page":"439","volume":"43","author":"Hoory S.","year":"2006","journal-title":"S.)"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(73)90031-2"},{"key":"atypb22","unstructured":"S. Jaggi,\n                      Design and Analysis of Network Codes\n                      , PhD thesis, California Institute of Technology, Pasadena, CA, 2006."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.847712"},{"key":"atypb24","first-page":"69","author":"Karger D. R.","year":"1998","journal-title":"New York"},{"key":"atypb25","first-page":"153","author":"Kawarabayashi K.","year":"2010","journal-title":"NJ"},{"key":"atypb26","first-page":"11","author":"Koetter R.","year":"2003","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"atypb27","first-page":"96","author":"Lau L. C.","year":"2010","journal-title":"Berlin"},{"key":"atypb28","first-page":"1743","author":"Li S. R.","year":"2006","journal-title":"NJ"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.807285"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70504-1"},{"key":"atypb33","first-page":"248","author":"Mucha M.","year":"2004","journal-title":"NJ"},{"key":"atypb34","unstructured":"A. Schrijver,\n                      Combinatorial Optimization\n                      , Springer, New York, 2003."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1504\/IJSNET.2010.033119"},{"key":"atypb37","first-page":"45","author":"Valiant L.","year":"1975","journal-title":"New York"},{"key":"atypb38","unstructured":"M. A. Woodbury,\n                      Inverting Modified Matrices\n                      , Memorandum Report 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950."},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"F. Zhang,\n                      The Schur Complement and Its Applications\n                      , Springer, New York, 2005.","DOI":"10.1007\/b105056"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110844970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:31Z","timestamp":1787337031000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110844970"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110844970"],"URL":"https:\/\/doi.org\/10.1137\/110844970","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}