{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:14Z","timestamp":1725558914776},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141614"},{"type":"electronic","value":"9783642141621"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14162-1_22","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:21Z","timestamp":1278321981000},"page":"261-272","source":"Crossref","is-referenced-by-count":1,"title":["Sparse Reliable Graph Backbones"],"prefix":"10.1007","author":[{"given":"Shiri","family":"Chechik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Emek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"22_CR1","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/rsa.3240060409","volume":"6","author":"N. Alon","year":"1995","unstructured":"Alon, N., Frieze, A., Welsh, D.: Polynomial time randomized approximation schemes for Tutte-Gr\u00f6thendieck invariants: the dense case. Random Struct. Algorithms\u00a06(4), 459\u2013478 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Ball, M.O., Colbourn, C.J., Provan, J.S.: Network reliability. In: Handbook of Operations Research: Network Models, pp. 673\u2013762. Elsevier North-Holland (1995)","DOI":"10.1016\/S0927-0507(05)80128-8"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A., Karger, D.R.: Approximating s\u2009\u2212\u2009t minimum cuts in $\\tilde{O} (n^2)$ time. In: Proc. 28th ACM Symp. on the Theory of Computing (STOC), pp. 47\u201355 (1996)","DOI":"10.1145\/237814.237827"},{"key":"22_CR4","series-title":"Graduate texts in mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Graduate texts in mathematics. Springer, Berlin (1998)"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1017\/CBO9780511662041.007","volume-title":"Matroid Applications","author":"T.H. Brylawski","year":"1992","unstructured":"Brylawski, T.H., Oxley, J.G.: The Tutte polynomial and its applications. In: White, N. (ed.) Matroid Applications, pp. 123\u2013225. Cambridge Univ. Press, Cambridge (1992)"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Batson, J.D., Spielman, D.A., Srivastava, N.: Twice-ramanujan sparsifiers. In: Proc. of the 41st ACM Symp. on Theory of Computing (STOC), pp. 255\u2013262 (2009)","DOI":"10.1145\/1536414.1536451"},{"issue":"7","key":"22_CR7","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.ic.2008.04.003","volume":"206","author":"L.A. Goldberg","year":"2008","unstructured":"Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. Inf. Comput.\u00a0206(7), 908\u2013929 (2008)","journal-title":"Inf. Comput."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Phil. SOC.\u00a0108, 35\u201353 (1990)","journal-title":"Math. Proc. Camb. Phil. SOC."},{"issue":"5","key":"22_CR9","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"M. Jerrum","year":"1993","unstructured":"Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. (SICOMP)\u00a022(5), 1087\u20131116 (1993)","journal-title":"SIAM J. Comput. (SICOMP)"},{"issue":"2","key":"22_CR10","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1137\/S0097539796298340","volume":"29","author":"D.R. Karger","year":"1999","unstructured":"Karger, D.R.: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J. Comput. (SICOMP)\u00a029(2), 492\u2013514 (1999)","journal-title":"SIAM J. Comput. (SICOMP)"},{"issue":"2","key":"22_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1287\/moor.24.2.383","volume":"24","author":"D.R. Karger","year":"1999","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. Mathematics of Operations Research (MOR)\u00a024(2), 383\u2013413 (1999)","journal-title":"Mathematics of Operations Research (MOR)"},{"issue":"2","key":"22_CR12","first-page":"47","volume":"8","author":"M.V. Lomonosov","year":"1972","unstructured":"Lomonosov, M.V., Polesskii, V.P.: Lower bound of network reliability. Probl. Peredachi Inf.\u00a08(2), 47\u201353 (1972)","journal-title":"Probl. Peredachi Inf."},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0016-0032(56)90044-8","volume":"263","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F., Shannon, C.E.: Reliable circuits using less reliable relays. J. Franklin Inst.\u00a0 262, 191\u2013208, 263, 281\u2013297 (1956)","journal-title":"J. Franklin Inst."},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. of Graph Theory"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. on Computing\u00a018, 740\u2013747 (1989)","journal-title":"SIAM J. on Computing"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proc. of the 36th ACM Symp. on Theory of Computing (STOC), pp. 81\u201390 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"22_CR17","unstructured":"Spielman, D.A., Teng, S.-H.: Spectral sparsification of graphs (2008), http:\/\/arxiv.org\/abs\/0808.4134"},{"issue":"3","key":"22_CR18","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. (SICOMP)\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput. (SICOMP)"}],"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-14162-1_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:07Z","timestamp":1606186087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14162-1_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141614","9783642141621"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14162-1_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}