{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:11:04Z","timestamp":1725495064788},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540429852"},{"type":"electronic","value":"9783540456780"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45678-3_48","type":"book-chapter","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T11:12:14Z","timestamp":1195125134000},"page":"562-574","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Some Basic Problems for Dynamic Process Graphs"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Jakoby","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maciej","family":"Li\u015bkiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,12,4]]},"reference":[{"key":"48_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1051\/ita\/1996300100011","volume":"30","author":"E. Allender","year":"1996","unstructured":"E. Allender and M. Ogihara, Relationships among PL, L, and the determinant, RAIRO-Theoretical Informatics and Applications, Vol. 30, 1996, 1\u201321.","journal-title":"RAIRO-Theoretical Informatics and Applications"},{"key":"48_CR2","unstructured":"A. Chiu, G. Davida, and B. Litow NC1 Division, Unpublished manuscript, 1999."},{"key":"48_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/jpdc.1995.1005","volume":"24","author":"H. El-Rewini","year":"1995","unstructured":"H. El-Rewini and H. H. Ali, Static Scheduling of Conditional Branches in Parallel Programs, J. Par. Distrib. Comput. 24, 1995, 41\u201354.","journal-title":"J. Par. Distrib. Comput."},{"key":"48_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/BFb0028563","volume-title":"Complexity of Problems on Graphs Represented as OBDDs","author":"J. Feigenbaum","year":"1998","unstructured":"J. Feigenbaum, S. Kannan, M. Vardi, and M. Viswanathan, Complexity of Problems on Graphs Represented as OBDDs, LNCS Proc. 15. STACS\u201998, 1998, 216\u2013226."},{"key":"48_CR5","first-page":"183","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin and A. Wigderson, Succinct Representations of Graphs, Information and Control, 56, 1983, 183\u2013198.","journal-title":"Succinct Representations of Graphs"},{"key":"48_CR6","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide To the Theory of NP-Completeness, Freeman, 1979."},{"key":"48_CR7","doi-asserted-by":"crossref","unstructured":"R. Greenlaw, H. J. Hoover, and W. L. Ruzzo, Limits to Parallel Computation-P-Completeness Theory, Oxford University Press, 1994.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"48_CR8","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1109\/12.102826","volume":"40","author":"S. Ha","year":"1991","unstructured":"S. Ha and E. Lee, Compile-time Scheduling and Assignment of Data-flow Program Graphs with Data-dependent Iteration, IEEE Trans. Computers 40, 1991, 1225\u20131238.","journal-title":"IEEE Trans. Computers"},{"key":"48_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/3-540-49116-3_36","volume-title":"Scheduling Dynamic Graphs","author":"A. Jakoby","year":"1999","unstructured":"A. Jakoby, M. Li\u015bkiewicz, and R. Reischuk, Scheduling Dynamic Graphs, LNCS Proc. 16. STACS\u201999, 1999, 383\u2013392."},{"key":"48_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/3-540-40064-8_22","volume-title":"The Expressive Power and Complexity of Dynamic Process Graphs","author":"A. Jakoby","year":"2000","unstructured":"A. Jakoby, M. Li\u015bkiewicz, and R. Reischuk, The Expressive Power and Complexity of Dynamic Process Graphs, LNCS Proc. 26. WG\u201900, 2000, 230\u2013243."},{"key":"48_CR11","unstructured":"A. Jakoby, M. Li\u015bkiewicz, and R. Reischuk, Approximating Schedules for Dynamic Graphs Efficiently, ECCC report TR01-038, 2001."},{"key":"48_CR12","first-page":"63","volume":"44","author":"T. Lengauer","year":"1992","unstructured":"T. Lengauer, K. Wagner, The Correlation between the Complexities of the Nonhierarchical and Hierarchical Versions of Graph Problems, J. CSS44, 1992, 63\u201393.","journal-title":"J. CSS"},{"key":"48_CR13","unstructured":"C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994."},{"key":"48_CR14","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C. Papadimitriou","year":"1986","unstructured":"C. Papadimitriou and M. Yannakakis, A Note on Succinct Representations of Graphs, Information and Control, 71, 1986, 181\u2013185.","journal-title":"Information and Control"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0219021","volume":"19","author":"C. Papadimitriou","year":"1990","unstructured":"C. Papadimitriou and M. Yannakakis, Towards an Architecture-Independent Analysis of Parallel Algorithms, SIAM J. Comput. 19, 1990, 322\u2013328.","journal-title":"SIAM J. Comput."},{"key":"48_CR16","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, The Complexity of Enumeration and Reliability Problems, SIAM J. Comput, Vol. 8, No. 3, 1979.","DOI":"10.1137\/0208032"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45678-3_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T17:01:34Z","timestamp":1630083694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45678-3_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540429852","9783540456780"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45678-3_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]}}}