{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T22:32:58Z","timestamp":1648506778326},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1988,5,1]],"date-time":"1988-05-01T00:00:00Z","timestamp":578448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Zeitschrift f\u00fcr Operations Research"],"published-print":{"date-parts":[[1988,5]]},"DOI":"10.1007\/bf01928922","type":"journal-article","created":{"date-parts":[[2005,7,24]],"date-time":"2005-07-24T18:04:47Z","timestamp":1122228287000},"page":"201-211","source":"Crossref","is-referenced-by-count":3,"title":["The computational complexity of graph problems with succinct multigraph representation"],"prefix":"10.1007","volume":"32","author":[{"given":"M.","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"K. W.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01928922_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"SA Cook","year":"1985","unstructured":"Cook SA (1985) A taxonomy of problems with fast parallel algorithms. Information and Control 64:2\u201322","journal-title":"Information and Control"},{"key":"BF01928922_CR2","first-page":"1","volume-title":"Research Report #RJ 5902","author":"E Dahlhaus","year":"1987","unstructured":"Dahlhaus E, Karpinski M (1987) Perfect matching for regular graphs is AC\u00b0-hard for the general matching problem. Research Report #RJ 5902, IBM Research, San Jose, pp 1\u20137"},{"key":"BF01928922_CR3","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H Galperin","year":"1983","unstructured":"Galperin H, Wigderson A (1983) Succinct representations of graphs. Information and Control 56:183\u2013198","journal-title":"Information and Control"},{"key":"BF01928922_CR4","doi-asserted-by":"crossref","unstructured":"Grigoriev DYu, Karpinski M (1987) The matching problem for bipartite graphs with polynomially bounded permanents is in NC. Proc. 28th IEEE FOCS, pp 166\u2013172","DOI":"10.1109\/SFCS.1987.56"},{"key":"BF01928922_CR5","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M, Lovasz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. To appear in Springer-Verlag","DOI":"10.1007\/978-3-642-97881-4"},{"key":"BF01928922_CR6","first-page":"85","volume-title":"Reducibilities among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibilities among combinatorial problems. Proc. IBM Symposium on Complexity of Computer Computation, Plenum Press, New York, pp 85\u2013103"},{"key":"BF01928922_CR7","doi-asserted-by":"crossref","unstructured":"Karp RM, Upfal E, Wigderson A (1985) Constructing a perfect matching is in random NC. Proc. 17th STOC, pp 22\u201332","DOI":"10.1145\/22145.22148"},{"key":"BF01928922_CR8","doi-asserted-by":"crossref","unstructured":"Lengauer T (1982) The complexity of compacting hierarchically specified layouts of integrated circuits. Proc. 23rd IEEE FOCS, pp 358\u2013368","DOI":"10.1109\/SFCS.1982.92"},{"key":"BF01928922_CR9","first-page":"180","volume":"226","author":"T Lengauer","year":"1986","unstructured":"Lengauer T (1986) Exploiting hierarchy in VLSI design. Proc. Aegean Workshop on Computing, Loutraki, LNCS 226:180\u2013193","journal-title":"LNCS"},{"key":"BF01928922_CR10","first-page":"100","volume":"247","author":"T Lengauer","year":"1987","unstructured":"Lengauer T, Wagner KW (1987) The correlation between the complexities of the non-hierarchical and hierarchical versions of graph problems. Proc. STACS 1987, LNCS 247:100\u2013113","journal-title":"LNCS"},{"key":"BF01928922_CR11","unstructured":"Lengauer T, Wagner KW (1987) The binary network flow problem is logspace complete for P. TR 138, Institute of Mathematics, University of Augsburg"},{"key":"BF01928922_CR12","doi-asserted-by":"crossref","unstructured":"Mulmuley K, Vazirani UV, Vazirani VV (1987) Matching is as easy as matrix inversion. Proc. 19th ACM STOC, pp 345\u2013354","DOI":"10.1145\/28395.383347"},{"key":"BF01928922_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"ChH Papadimitriou","year":"1986","unstructured":"Papadimitriou ChH, Yannakakis M (1986) A note on succinct representations of graphs. Information and Control 71:181\u2013185","journal-title":"Information and Control"},{"key":"BF01928922_CR14","first-page":"544","volume":"176","author":"KW Wagner","year":"1984","unstructured":"Wagner KW (1984) The complexity of problems concerning graphs with regularities. Proc. of MFCS Conference 1984, LNCS 176:544\u2013552","journal-title":"LNCS"}],"container-title":["Zeitschrift f\u00fcr Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01928922.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01928922\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01928922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T09:56:14Z","timestamp":1586339774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01928922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,5]]},"references-count":14,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1988,5]]}},"alternative-id":["BF01928922"],"URL":"https:\/\/doi.org\/10.1007\/bf01928922","relation":{},"ISSN":["0340-9422","1432-5217"],"issn-type":[{"value":"0340-9422","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,5]]}}}