{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:40Z","timestamp":1725663160193},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514862"},{"type":"electronic","value":"9783540481768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51486-4_66","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:57:33Z","timestamp":1330203453000},"page":"185-195","source":"Crossref","is-referenced-by-count":0,"title":["Parallel complexity of lexicographically first problems for tree-structured graphs"],"prefix":"10.1007","author":[{"given":"Bogdan","family":"Chlebus","sequence":"first","affiliation":[]},{"given":"Krzysztof","family":"Diks","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Szymacha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(87)90105-0","volume":"24","author":"R. Anderson","year":"1978","unstructured":"R. Anderson,E.W. Meyr, Parallelism and the maximal path problem. Inf.Procc.Letters 24 (1978) 121\u2013126.","journal-title":"Inf.Procc.Letters"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"S.Arnborg,J.Lagergren,D.Seese, Problems easy for tree-decomposable graphs. ICALP (1988) 38\u201351.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"14_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg, Efficient Algorithms for combinatorial problems on graphs with bounded decomposability \u2014 a survey. BIT 25 (1985), 2\u201333.","journal-title":"BIT"},{"key":"14_CR4","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg,D.G. Corneil,A. Proskurowski, Complexity of finding embeddings in a k-tree. SIAM J.Alg. and Discr. Methods 8 (1987), 277\u2013284.","journal-title":"SIAM J.Alg. and Discr. Methods"},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0196-6774(87)90039-3","volume":"8","author":"W. M. Bern","year":"1987","unstructured":"W.M. Bern,E.L. Lawler and A.L. Wong, Linear time computation of optimal subgraphs of decomposable graphs. J. of Algorithms 8(1987) 216\u2013235.","journal-title":"J. of Algorithms"},{"key":"14_CR6","unstructured":"H.L. Bodlaender, Classes of graphs with bounded tree-width, Preprint, Dec 1986."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, Dynamic programming on graphs with bounded tree width, ICALP (1988).","DOI":"10.1007\/3-540-19488-6_110"},{"key":"14_CR8","unstructured":"H.L. Bodlaender, Polynomial algorithms for chromatic index and graph isomorphism on patrial k-trees. Technical Report RUU-CS-87-17 Dept.of Comp.Science, Univ. of Utrecht, Utrecht, 1987."},{"key":"14_CR9","unstructured":"H.L.Bodlaender, NC-algorithms for graphs with small tree width. Technical Report RUU-CS-88-4."},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"B.S.Chlebus,K.Diks,T.Radzik, Testing isomorphism of outerplanar graphs in parallel. Proc. MFCS (1988).","DOI":"10.1007\/BFb0017145"},{"key":"14_CR11","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. Inf.Control 64(1985) 2\u201322.","journal-title":"Inf.Control"},{"key":"14_CR12","unstructured":"K.Diks, T.Hagerup, W.Rytter, Optimal parallel algorithms for the recognition and coloring outerplanar graphs. This proceedings."},{"key":"14_CR13","unstructured":"A.Gibbons,W.Rytter, Efficient parallel algorithms. Cambridge University Press (1988)."},{"key":"14_CR14","unstructured":"A.Gibbons, W.Rytter, Fast parallel edge coloring of tree structured graphs. FCT (1987)."},{"key":"14_CR15","unstructured":"S.Miyano, The lexicographically first maximal subgraph problems: P-completeness and NC algorithms. ICALP'87."},{"key":"14_CR16","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"J. Reif","year":"1985","unstructured":"J. Reif, Depth first search is inherently sequential. Inf.Proc.Lettres 20(1985) 229\u2013234.","journal-title":"Inf.Proc.Lettres"},{"key":"14_CR17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. Seymour, Graph minors II. Algoritmic aspects of tree width. J. of Algorithms, 7:309\u2013322, 1986.","journal-title":"J. of Algorithms"},{"key":"14_CR18","unstructured":"W.Rytter,T.Szymacha, Parallel algorithms for a clas of graphs defined recursively. Accepted for Inf. Proc. Letters."},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"W.Rytter, The complexity of two way pushdown automata and recursive programs. Combinatorial algorithms on words (ed.A.Apostolico, Z.Galil) Springer-Verag (1985).","DOI":"10.1007\/978-3-642-82456-2_24"},{"issue":"2","key":"14_CR20","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0020-0190(82)90086-2","volume":"14","author":"A. Slisenko","year":"1982","unstructured":"A. Slisenko, Context-free grammars as a tool for describing polynomial time subclasses of hard problems. Inf.Proc.Letters 14:2 (1982) 52\u201357.","journal-title":"Inf.Proc.Letters"},{"key":"14_CR21","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1137\/0215058","volume":"15","author":"J. Smith","year":"1986","unstructured":"J. Smith, Parallel algorithms for depth first search. I. Planar graphs. SIAM J.Comp. 15 (1986) 814\u2013830.","journal-title":"I. Planar graphs. SIAM J.Comp."},{"key":"14_CR22","unstructured":"M.M.Syslo, NP-complete problems on some tree-structured graphs: a review. In M.Nagl and J.Perl, editors, Proc.WG'83 International Workshop on Graph Therotecic Concepts in Computer Science, 342\u2013353, (1983)."},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"R.Tarjan, U.Vishkin, Finding biconnected components and computing tree functions in logarithmic parallel time. 25th IEEE FOCS (1984) 12\u201320.","DOI":"10.1109\/SFCS.1984.715896"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1989"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51486-4_66.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:22Z","timestamp":1605648082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51486-4_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514862","9783540481768"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-51486-4_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}