{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:24:23Z","timestamp":1725495863282},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540654735"},{"type":"electronic","value":"9783540376231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-37623-2_22","type":"book-chapter","created":{"date-parts":[[2007,11,19]],"date-time":"2007-11-19T12:45:17Z","timestamp":1195476317000},"page":"288-301","source":"Crossref","is-referenced-by-count":3,"title":["NP-Completeness of Some Tree-Clustering Problems"],"prefix":"10.1007","author":[{"given":"Falk","family":"Schreiber","sequence":"first","affiliation":[]},{"given":"Konstantinos","family":"Skodinis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,1,15]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277\u2013384, 1987.","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"2","key":"22_CR2","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1145\/322003.322005","volume":"24","author":"F. T. Boesch","year":"1977","unstructured":"F. T. Boesch and J. F. Gimpel. Covering the points of a digraph with point-disjoint paths and its application to code optimization. J. Assoc. Comput. Mach., 24(2):192\u2013198, 1977.","journal-title":"J. Assoc. Comput. Mach."},{"key":"22_CR3","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/3-540-63938-1_59","volume-title":"Proc. of Graph Drawing","author":"F. J. Brandenburg","year":"1997","unstructured":"F. J. Brandenburg. Graph clustering I: Cycles of cliques. In G. Di Battista, editor, Proc. of Graph Drawing, volume 1353 of Lect. Notes in Comput. Sci., pages 158\u2013168. Springer-Verlag, New York\/Berlin, 1997."},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0885-064X(91)90006-J","volume":"7","author":"E. Cohen","year":"1991","unstructured":"E. Cohen and M. Tarsi. NP-completeness of graph decomposition problems. J. Complexity, 7:200\u2013212, 1991.","journal-title":"J. Complexity"},{"issue":"4","key":"22_CR5","doi-asserted-by":"publisher","first-page":"1166","DOI":"10.1137\/S0097539792229507","volume":"26","author":"D. Dor","year":"1997","unstructured":"D. Dor and M. Tarsi.Graph decomposition is NP-complete: A complete proof of holyer\u2019s conjecture. SIAM J. Comput., 26(4):1166\u20131187, 1997.","journal-title":"SIAM J. Comput"},{"key":"22_CR6","series-title":"Lect. Notes in Comput. Sci.","first-page":"101","volume-title":"Proc. of Graph Drawing","author":"P. Eades","year":"1996","unstructured":"P. Eades and Q.-W. Feng. Multilevel visualization of clustered graphs. In S. North, editor, Proc. of Graph Drawing, volume 1190 of Lect. Notes in Comput. Sci., pages 101\u2013112. Springer-Verlag, New York\/Berlin, 1996."},{"key":"22_CR7","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/BFb0030816","volume-title":"Computing and Combinatorics","author":"Q.-W. Feng","year":"1995","unstructured":"Q.-W. Feng, R. F. Cohen, and P. Eades. How to draw a planar clustered graph. In D.-Z. Du, editor, Computing and Combinatorics, volume 959 of Lect. Notes in Comput. Sci., pages 21\u201330. Springer-Verlag, New York\/Berlin, 1995."},{"issue":"11","key":"22_CR8","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1002\/spe.4380211102","volume":"21","author":"T. Fruchterman","year":"1991","unstructured":"T. Fruchterman and E. Reingold. Graph drawing by force-directed placement. Software-Practice and Experience, 21(11):1129\u20131164, 1991.","journal-title":"Software-Practice and Experience"},{"key":"22_CR9","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability;A guide to the theory of NP-completeness. W. H. Freeman, 1979."},{"key":"22_CR10","series-title":"Lect. Notes in Comput. Sci.","first-page":"233","volume-title":"Proc. of Graph Drawing","author":"M. Himsolt","year":"1996","unstructured":"M. Himsolt. The graphlet system. In S. North, editor, Proc. of Graph Drawing, volume 1190 of Lect. Notes in Comput. Sci., pages 233\u2013240. Springer-Verlag, New York\/Berlin, 1996."},{"issue":"4","key":"22_CR11","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer. The NP-completeness of some edge-partition problems. SIAM J. Comput., 10(4):713\u2013717, 1981.","journal-title":"SIAM J. Comput."},{"key":"22_CR12","unstructured":"J. Kratochvil, M. Goljan, and P. Kucaera. String graphs. Technical report, Academia Prague, 1986."},{"key":"22_CR13","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994."},{"key":"22_CR14","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-63938-1_71","volume-title":"Proc. of Graph Drawing","author":"T. Roxborough","year":"1997","unstructured":"T. Roxborough and A. Sen. Graph clustering using multiway ratio cut. In G. Di-Battista, editor, Proc. of Graph Drawing, volume 1353 of Lect. Notes in Comput. Sci., pages 291\u2013296. Springer-Verlag, New York\/Berlin, 1997."},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"11","author":"K. Sugiyama","year":"1981","unstructured":"K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Transactions on Systems, Man and Cybernetics, 11:109\u2013125, 1981.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-37623-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T17:48:02Z","timestamp":1551116882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-37623-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540654735","9783540376231"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-37623-2_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}