{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:05Z","timestamp":1725664085657},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_33","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:24Z","timestamp":1330270644000},"page":"359-369","source":"Crossref","is-referenced-by-count":2,"title":["A parallel algorithm for edge-coloring partial k-trees"],"prefix":"10.1007","author":[{"given":"Xiao","family":"Zhou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shin-ichi","family":"Nakano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takao","family":"Nishizeki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"issue":"5","key":"33_CR1","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese, An algebraic theory of graph reduction, Journal of the Association for Computing Machinery, 40, 5, pp.1134\u20131164, 1993.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"2","key":"33_CR2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg and J. Lagergren, Easy problems for tree-decomposable graphs, Journal of Algorithms, 12, 2, pp.308\u2013340, 1991.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"33_CR3","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H. L. Bodlaender","year":"1990","unstructured":"H. L. Bodlaender, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, Journal of Algorithms, 11, 4, pp.631\u2013643, 1990.","journal-title":"Journal of Algorithms"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, Proc. of the 25th Ann. ACM Symp. on Theory of Computing, pp.226\u2013234, San Diego, CA, 1993.","DOI":"10.1145\/167088.167161"},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R. B. Borie","year":"1992","unstructured":"R.B. Borie, R.G. Parker and C.A. Tovey, Automatic generation of lineartime algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, pp.555\u2013581, 1992.","journal-title":"Algorithmica"},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle, The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation, 85, pp.12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"33_CR7","volume-title":"A near-optimal parallel algorithm for edge-coloring outerplanar graphs","author":"Y. Caspi","year":"1992","unstructured":"Y. Caspi and E. Dekel, A near-optimal parallel algorithm for edge-coloring outerplanar graphs, manuscript, Computer Science Program, University of Texas at Dallas, Richardson, Tx., 1992."},{"key":"33_CR8","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/0196-6774(90)90032-A","volume":"11","author":"M. Chrobak","year":"1990","unstructured":"M. Chrobak and T. Nishizeki, Improved edge-coloring algorithms for planar graphs, J. Algorithms, 11, pp.102\u2013116, 1990.","journal-title":"J. Algorithms"},{"key":"33_CR9","volume-title":"Edge-Colouring of Graphs","author":"S. Fiorini","year":"1977","unstructured":"S. Fiorini and R.J. Wilson, Edge-Colouring of Graphs, Pitman, London, 1977."},{"key":"33_CR10","volume-title":"Efficient Parallel Algorithms","author":"A. Gibbons","year":"1988","unstructured":"A. Gibbons and W. Rytter, Efficient Parallel Algorithms, Cambridge Univ. Press, Cambridge, 1988."},{"key":"33_CR11","unstructured":"H. N. Gabow, T. Nishizeki, O. Kariv, D. Leven and O. Terada, Algorithm for edge-coloring graphs, Tech. Rep. TRECIS-8501, Tohoku Univ., 1985."},{"key":"33_CR12","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. J. Holyer","year":"1981","unstructured":"I.J. Holyer, The NP-completeness of edge-coloring, SIAM J. on Computing, 10, pp.718\u2013720, 1981.","journal-title":"SIAM J. on Computing"},{"key":"33_CR13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/jgt.3190100202","volume":"10","author":"S. L. Hakimi","year":"1986","unstructured":"S. L. Hakimi and O. Kariv, On a generalization of edge-coloring in graphs, Journal of Graph Theory, 10, pp.139\u2013154, 1986.","journal-title":"Journal of Graph Theory"},{"key":"33_CR14","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","volume":"8","author":"H. J. Karloff","year":"1985","unstructured":"H. J. Karloff and D. B. Shmoys, Efficient parallel algorithms for edge-coloring problems, Journal of Algorithms, 8, pp.39\u201352, 1985.","journal-title":"Journal of Algorithms"},{"key":"33_CR15","volume-title":"Planar Graphs: Theory and Algorithms","author":"T. Nishizeki","year":"1988","unstructured":"T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms, North-Holland, Amsterdam, 1988."},{"issue":"No.3","key":"33_CR16","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1109\/31.1747","volume":"35","author":"S. Nakano","year":"1988","unstructured":"S. Nakano, T. Nishizeki and N. Saito, On the f-coloring multigraphs, IEEE Transactions on Circuits and Systems, Vol. 35, No. 3, pp. 345\u2013353, 1988.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"33_CR17","doi-asserted-by":"crossref","unstructured":"B.A. Reed, Finding approximate separators and computing tree-width quickly, Proc. of the 24th Ann. ACM Symp. on Theory of Computing, pp. 221\u2013228, 1992.","DOI":"10.1145\/129712.129734"},{"key":"33_CR18","first-page":"1382","volume":"11","author":"O. Terada","year":"1982","unstructured":"O. Terada and T. Nishizeki, Approximate algorithms for the edge-coloring of graphs, Trans. Inst. of Electronics and Communication Eng. of Japan, J65-D, 11, pp. 1382\u20131389, 1982.","journal-title":"Trans. Inst. of Electronics and Communication Eng. of Japan, J65-D"},{"issue":"3","key":"33_CR19","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, Journal of the Association for Computing Machinery, 29, 3, pp. 623\u2013641, 1982.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"33_CR20","doi-asserted-by":"crossref","unstructured":"X. Zhou, S. Nakano and T. Nishizeki, A linear algorithm for edge-coloring partial k-trees, Proc. of First Europian Symposium on Algorithms, Lect. Notes in Computer Science, Springer-Verlag, 726, pp. 409\u2013418, 1993.","DOI":"10.1007\/3-540-57273-2_76"},{"key":"33_CR21","unstructured":"X. Zhou, H. Suzuki and T. Nishizeki, Sequential and parallel algorithms for edge-coloring series-parallel multigraphs, Proc. of Third Conf. on Integer Programming and Combinatorial Optimization, pp. 129\u2013145, 1993."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:13:01Z","timestamp":1619572381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}