{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:59:00Z","timestamp":1725663540267},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540180883"},{"type":"electronic","value":"9783540477471"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18088-5_36","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:26:58Z","timestamp":1330180018000},"page":"425-434","source":"Crossref","is-referenced-by-count":2,"title":["The lexicographically first maximal subgraph problems: P-completeness and NC algorithms"],"prefix":"10.1007","author":[{"given":"Satoru","family":"Miyano","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"T. Asano and T. Hirata, Edge-deletion and edge-contraction problems, Proc. 14th ACM STOC (1982) 245\u2013254.","DOI":"10.1145\/800070.802198"},{"key":"36_CR2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"S.A. Cook, An observation on time-storage trade off, J. Comput. System Sci. 9 (1974) 308\u2013316.","journal-title":"J. Comput. System Sci."},{"key":"36_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S.A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. Contr. 64 (1985) 2\u201322.","journal-title":"Inform. Contr."},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"M.R. Garey and D.S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math. 32 (1977) 826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L. M. Goldschlager","year":"1977","unstructured":"L.M. Goldschlager, The monotone and planar circuit value problems are log space complete for P, SIGACT News 9 (1977) 25\u201329.","journal-title":"SIGACT News"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"D.B. Johnson and S.M. Venkatesan, Parallel algorithm for minimum cuts and maximum flows in planar networks, Proc. 22nd IEEE FOCS (1982) 244\u2013254.","DOI":"10.1109\/SFCS.1982.83"},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"R.M. Karp, E. Upfal and A. Wigderson, Constructing a perfect matching is in random NC, Proc. 17th ACM STOC (1985) 22\u201332.","DOI":"10.1145\/22145.22148"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. E. Ladner","year":"1975","unstructured":"R.E. Ladner, The circuit value problem is log-space complete for P, SIGACT News 7 (1975) 18\u201320.","journal-title":"SIGACT News"},{"key":"36_CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J. M. Lewis","year":"1980","unstructured":"J.M. Lewis and M. Yannakakis, The node deletion problems for hereditary properties is NP-complete, J. Comput. System Sci. 20 (1980) 219\u2013230.","journal-title":"J. Comput. System Sci."},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"M. Luby, A simple parallel algorithm for the maximal independent set problem, Proc. 17th ACM STOC (1985) 1\u201310.","DOI":"10.1145\/22145.22146"},{"key":"36_CR11","unstructured":"E. Speckenmeyer, Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen, Ph.D. Thesis, Universit\u00e4t Paderborn, 1983."},{"key":"36_CR12","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0166-218X(81)90039-1","volume":"3","author":"T. Watanabe","year":"1981","unstructured":"T. Watanabe, T. Ae and A. Nakamura, On the removal of forbidden graphs by edge-deletion or by edge-contraction, Discrete Appl. Math. 3 (1981) 151\u2013153.","journal-title":"Discrete Appl. Math."},{"key":"36_CR13","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM J. Comput. 10 (1981) 310\u2013327.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18088-5_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T17:13:48Z","timestamp":1619543628000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18088-5_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540180883","9783540477471"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-18088-5_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}