{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:30:45Z","timestamp":1710347445235},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1989,12,1]],"date-time":"1989-12-01T00:00:00Z","timestamp":628473600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Systems Theory"],"published-print":{"date-parts":[[1989,12]]},"DOI":"10.1007\/bf02088292","type":"journal-article","created":{"date-parts":[[2005,8,15]],"date-time":"2005-08-15T00:34:03Z","timestamp":1124066043000},"page":"47-73","source":"Crossref","is-referenced-by-count":21,"title":["The lexicographically first maximal subgraph problems:P-completeness andNC algorithms"],"prefix":"10.1007","volume":"22","author":[{"given":"Satoru","family":"Miyano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02088292_CR1","unstructured":"R. Anderson and E. W. Mayr, Parallelism and greedy algorithms, STAN-CS-84-1003, April 1984."},{"key":"BF02088292_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(87)90105-0","volume":"24","author":"R. Anderson","year":"1987","unstructured":"R. Anderson and E. W. Mayr, Parallelism and the maximal path problem,Inform. Process. Lett.,24 (1987), 121\u2013126.","journal-title":"Inform. Process. Lett."},{"key":"BF02088292_CR3","doi-asserted-by":"crossref","unstructured":"T. Asano and T. Hirata, Edge-deletion and edge-contraction problems,Proc. 14th ACM STOC, 1982, pp. 245\u2013254.","DOI":"10.1145\/800070.802198"},{"key":"BF02088292_CR4","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0304-3975(84)90024-0","volume":"32","author":"J. Avenhaus","year":"1984","unstructured":"J. Avenhaus and K. Madlener, The Nielsen reduction andP-complete problems in free groups,Theoret. Comput. Sci.,32 (1984), 61\u201374.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02088292_CR5","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Leuker, Testing for the consecutive ones property, interval graphs, and graph planarity usingPQ-tree algorithms,J. Comput. System Sci.,13 (1976), 335\u2013379.","journal-title":"J. Comput. System Sci."},{"key":"BF02088292_CR6","first-page":"433","volume":"4","author":"G. Chartrand","year":"1967","unstructured":"G. Chartrand and F. Harary, Planar permutation graphs,Ann. Inst. Henri Poincar\u00e9,4 (1967), 433\u2013438.","journal-title":"Ann. Inst. Henri Poincar\u00e9"},{"key":"BF02088292_CR7","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":"BF02088292_CR8","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. and Control,64 (1985), 2\u201322.","journal-title":"Inform. and Control"},{"key":"BF02088292_CR9","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0020-0190(79)90152-2","volume":"8","author":"D. Dobkin","year":"1979","unstructured":"D. Dobkin, R. J. Lipton, and S. Reiss, Linear programming is log-space hard forP, Inform. Process. Lett.,8 (1979), 96\u201397.","journal-title":"Inform. Process. Lett."},{"key":"BF02088292_CR10","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. T. Garey","year":"1977","unstructured":"M. T. Garey and D. S. Johnson, The rectilinear Steiner tree problem isNP-complete,SIAM J. Appl. Math.,32 (1977), 826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02088292_CR11","doi-asserted-by":"crossref","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 forP, SIGACT News,9 (1977), 25\u201329.","journal-title":"SIGACT News"},{"key":"BF02088292_CR12","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L. M. Goldschlager","year":"1982","unstructured":"L. M. Goldschlager, R. E. Shaw, and J. Staples, The maximum flow problem is log-space complete forP, Theoret. Comput. Sci.,21 (1982), 105\u2013111.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02088292_CR13","volume-title":"Graph Theory","author":"F. Harary","year":"1970","unstructured":"F. Harary,Graph Theory, Addison-Wesley, Reading, MA, 1970."},{"key":"BF02088292_CR14","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"J. E. Hopcroft and R. E. Tarjan, Efficient planarity testing,J. Assoc. Comput. Mach.,21 (1974), 549\u2013568.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02088292_CR15","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, pp. 244\u2013254.","DOI":"10.1109\/SFCS.1982.83"},{"key":"BF02088292_CR16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1977","unstructured":"N. D. Jones and W. T. Laaser, Complete problems for deterministic polynomial time,Theoret. Comput. Sci.,3 (1977), 105\u2013117.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02088292_CR17","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal, and A. Wigderson, Constructing a perfect matching is in randomNC, Proc. 17th ACM STOC, 1985, pp. 22\u201332.","DOI":"10.1145\/22145.22148"},{"key":"BF02088292_CR18","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal, and A. Wigderson, Are search and decision problems computationally equivalent?,Proc. 17th ACM STOC, 1985, pp. 464\u2013475.","DOI":"10.1145\/22145.22197"},{"key":"BF02088292_CR19","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal, and A. Wigderson, The complexity of parallel computation on matroids,Proc. 26th IEEE FOCS, 1985, pp. 229\u2013234.","DOI":"10.1109\/SFCS.1985.57"},{"key":"BF02088292_CR20","doi-asserted-by":"crossref","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 forP, SIGACT News,7 (1975), 18\u201321.","journal-title":"SIGACT News"},{"key":"BF02088292_CR21","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 isNP-complete,J. Comput. System Sci.,20 (1980), 219\u2013230.","journal-title":"J. Comput. System Sci."},{"key":"BF02088292_CR22","doi-asserted-by":"crossref","unstructured":"M. Luby, A simple parallel algorithm for the maximal independent set problem,Proc. 17th ACM STOC, 1985, pp. 1\u201310.","DOI":"10.1145\/22145.22146"},{"key":"BF02088292_CR23","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(86)90145-6","volume":"22","author":"C. U. Martel","year":"1986","unstructured":"C. U. Martel, Lower bounds on parallel algorithms for finding the first maximal independent set,Inform. Process. Lett.,22 (1986), 81\u201385.","journal-title":"Inform. Process. Lett."},{"key":"BF02088292_CR24","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"S. L. Mitchell","year":"1979","unstructured":"S. L. Mitchell, Linear algorithms recognize outerplanar and maximal outerplanar graphs,Inform. Process. Lett.,9 (1979), 229\u2013232.","journal-title":"Inform. Process. Lett."},{"key":"BF02088292_CR25","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0020-0190(88)90095-6","volume":"27","author":"S. Miyano","year":"1988","unstructured":"S. Miyano, A parallelizable lexicographically first maximal edge-induced subgraph problem,Inform. Process. Lett.,27 (1988), 75\u201378.","journal-title":"Inform. Process. Lett."},{"key":"BF02088292_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1007\/BFb0017168","volume-title":"Proc. 13th MFCS","author":"S. Miyano","year":"1988","unstructured":"S. Miyano, \u0394 2 p -complete lexicographically first maximal subgraph problems,Proc. 13th MFCS, Lecture Notes in Computer Science, Vol. 324, Springer-Verlag, Berlin, 1988, pp. 454\u2013462."},{"key":"BF02088292_CR27","unstructured":"S. Miyano, Parallel complexity andP-complete problems,Proc. FGCS '88, 1988, pp. 532\u2013541."},{"key":"BF02088292_CR28","doi-asserted-by":"crossref","unstructured":"N. Pippenger, On simultaneous resource bounds,Proc. 20th IEEE FOCS, 1979, pp. 307\u2013311.","DOI":"10.1109\/SFCS.1979.29"},{"key":"BF02088292_CR29","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. H. Reif","year":"1985","unstructured":"J. H. Reif, Depth-first search is inherently sequential,Inform. Process. Lett.,20 (1985), 229\u2013234.","journal-title":"Inform. Process. Lett."},{"key":"BF02088292_CR30","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo, On uniform circuit complexity,J. Comput. System Sci.,22 (1981), 365\u2013383.","journal-title":"J. Comput. System Sci."},{"key":"BF02088292_CR31","unstructured":"E. Speckenmeyer, Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen, Ph.D. Thesis, Universit\u00e4t-GH-Paderborn, 1983."},{"key":"BF02088292_CR32","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":"BF02088292_CR33","series-title":"Lecture Notes in Computer Science","first-page":"165","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Wiegers","year":"1986","unstructured":"M. Wiegers, Recognizing outerplanar graphs in linear time,Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 246, Springer-Verlag, Berlin, 1986, pp. 165\u2013176."},{"key":"BF02088292_CR34","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":["Mathematical Systems Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02088292.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02088292\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02088292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T01:17:30Z","timestamp":1586395050000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02088292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,12]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,12]]}},"alternative-id":["BF02088292"],"URL":"https:\/\/doi.org\/10.1007\/bf02088292","relation":{},"ISSN":["0025-5661","1433-0490"],"issn-type":[{"value":"0025-5661","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,12]]}}}