{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:53Z","timestamp":1725514433933},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_51","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"566-572","source":"Crossref","is-referenced-by-count":1,"title":["Maximum Edge-Disjoint Paths Problem in Planar Graphs"],"prefix":"10.1007","author":[{"given":"Mingji","family":"Xia","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"51_CR1","unstructured":"Brandes, U., Neyer, G., Wagner, D.: Edge-disjoint paths in planar graphs with short total length. Technical Reports (1996)"},{"key":"51_CR2","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1103\/PhysRev.124.1664","volume":"124","author":"M.E. Fishier","year":"1961","unstructured":"Fishier, M.E.: Statistical mechanics of dimers on a plane lattice. Phys. Rev.\u00a0124, 1664\u20131672 (1961)","journal-title":"Phys. Rev."},{"key":"51_CR3","doi-asserted-by":"publisher","first-page":"1209","DOI":"10.1016\/0031-8914(61)90063-5","volume":"27","author":"P.W. Kasteleyn","year":"1961","unstructured":"Kasteleyn, P.W.: The statistics of dimers on a lattice. Physica\u00a027, 1209\u20131225 (1961)","journal-title":"Physica"},{"key":"51_CR4","first-page":"43","volume-title":"Graph Theory and Theoretical Physics","author":"P.W. Kasteleyn","year":"1967","unstructured":"Kasteleyn, P.W.: Graph theory and crystal physics. In: Harary, F. (ed.) Graph Theory and Theoretical Physics, pp. 43\u2013110. Academic Press, London (1967)"},{"key":"51_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01202792","volume":"13","author":"M. Middendorf","year":"1993","unstructured":"Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint paths problem. Combinatorica\u00a013, 97\u2013107 (1993)","journal-title":"Combinatorica"},{"key":"51_CR6","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"51_CR7","volume-title":"Combinatorial Optimization: Polyhedra and Efficieny","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficieny. Springer, Heidelberg (2003)"},{"key":"51_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1006\/jctb.1993.1062","volume":"59","author":"A. Seb\u0151","year":"1993","unstructured":"Seb\u0151, A.: Integer plane multiflows with a fixed number of demands. J. Comb. Theory Ser. B\u00a059, 163\u2013171 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"key":"51_CR9","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1080\/14786436108243366","volume":"6","author":"H.N.V. Temperley","year":"1961","unstructured":"Temperley, H.N.V., Fishier, M.E.: Dimer problems in statistical mechanics - An exact result. Philosophical Magazine\u00a06, 1061\u20131063 (1961)","journal-title":"Philosophical Magazine"},{"key":"51_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01294465","volume":"15","author":"D. Wagner","year":"1995","unstructured":"Wagner, D., Weihe, K.: A linear-time algorithm for edge-disjoint paths in planar graphs. Combinatorica\u00a015, 135\u2013150 (1995)","journal-title":"Combinatorica"},{"key":"51_CR11","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S.P. Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing\u00a031, 398\u2013427 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR12","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 Journal on Computing\u00a08, 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR13","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/S0097539700377025","volume":"31","author":"L.G. Valiant","year":"2002","unstructured":"Valiant, L.G.: Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing\u00a031, 1229\u20131254 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR14","unstructured":"Valiant, L.G.: Holographic algorithms (extended abstract). In: FOCS, 2004, pp. 306\u2013315 (2004)"},{"key":"51_CR15","unstructured":"Valiant, L.G.: Accidental Algorithms. In: FOCS, 2006, pp. 509\u2013517 (2006)"},{"key":"51_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1007\/11811305_39","volume-title":"Theory and Applications of Models of Computation","author":"W.-B. Zhao","year":"2006","unstructured":"Zhao, W.-B., Xia, M.: #3-Regular Bipartite Planar Vertex Cover is #P-Complete. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 356\u2013364. Springer, Heidelberg (2006)"},{"key":"51_CR17","unstructured":"Zhang, P., Zhao, W.: On the complexity and approximation fo the min-sum and min-max disjoint paths problems. Manuscripts."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:25Z","timestamp":1619516305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_51","relation":{},"subject":[]}}