{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:02:44Z","timestamp":1725552164794},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310006"},{"type":"electronic","value":"9783540314684"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11604686_7","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T15:02:01Z","timestamp":1133794921000},"page":"69-80","source":"Crossref","is-referenced-by-count":7,"title":["Minimizing NLC-Width is NP-Complete"],"prefix":"10.1007","author":[{"given":"Frank","family":"Gurski","sequence":"first","affiliation":[]},{"given":"Egon","family":"Wanke","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"7_CR1","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods\u00a08(2), 227\u2013284 (1987)","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"issue":"5","key":"7_CR2","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D.: An algebraic theory of graph reduction. Journal of the ACM\u00a040(5), 1134\u20131164 (1993)","journal-title":"Journal of the ACM"},{"issue":"2","key":"7_CR3","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms\u00a018(2), 238\u2013255 (1995)","journal-title":"Journal of Algorithms"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/10719839_14","volume-title":"LATIN 2000: Theoretical Informatics","author":"D.G. Corneil","year":"2000","unstructured":"Corneil, D.G., Habib, M., Lanlignel, J.M., Reed, B., Rotics, U.: Polynomial time recognition of clique-width at most three graphs. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 126\u2013134. Springer, Heidelberg (2000)"},{"issue":"4","key":"7_CR5","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM Journal on Computing\u00a014(4), 926\u2013934 (1985)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"7_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Applied Mathematics\u00a0101, 77\u2013114 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"W. Espelage","year":"2001","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandst\u00e4dt, A., Van Le, B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 117\u2013128. Springer, Heidelberg (2001)"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-540-24698-5_16","volume-title":"LATIN 2004: Theoretical Informatics","author":"F. Gurski","year":"2004","unstructured":"Gurski, F., Wanke, E.: Vertex disjoint paths on clique-width bounded graphs (Extended abstract). In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 119\u2013128. Springer, Heidelberg (2004)"},{"key":"7_CR10","unstructured":"Gurski, F., Wanke, E.: Line graphs of bounded clique-width Manuscript (submitted) (2005), available at http:\/\/www.acs.uni-duesseldorf.de\/~gurski"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Gurski, F., Wanke, E.: On the relationship between NLC-width and linear NLC-width. Manuscript, accepted for Theoretical Computer Science (2005)","DOI":"10.1016\/j.tcs.2005.05.018"},{"key":"7_CR12","first-page":"39","volume":"132","author":"\u00d6. Johansson","year":"1998","unstructured":"Johansson, \u00d6.: Clique-decomposition, NLC-decomposition, and modular decomposition - relationships and results for random graphs. Congressus Numerantium\u00a0132, 39\u201360 (1998)","journal-title":"Congressus Numerantium"},{"issue":"3","key":"7_CR13","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1142\/S0129054100000223","volume":"11","author":"\u00d6. Johansson","year":"2000","unstructured":"Johansson, \u00d6.: NLC2-decomposition in polynomial time. International Journal of Foundations of Computer Science\u00a011(3), 373\u2013395 (2000)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"2-3","key":"7_CR14","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics\u00a0126(2-3), 197\u2013221 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"7_CR15","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1145\/321850.321853","volume":"21","author":"P.G.H. Lehot","year":"1974","unstructured":"Lehot, P.G.H.: An optimal algorithm to detect a line graph and output its root graph. Journal of the ACM\u00a021(4), 569\u2013575 (1974)","journal-title":"Journal of the ACM"},{"key":"7_CR16","unstructured":"Lozin, V., Rautenbach, D.: The tree- and clique-width of bipartite graphs in special classes. Technical Report RRR 33-2004, Rutgers University (2004)"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors I. Excluding a forest. Journal of Combinatorial Theory, Series B\u00a035, 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II. Algorithmic aspects of tree width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E. Wanke","year":"1994","unstructured":"Wanke, E.: k-NLC graphs and polynomial algorithms. Discrete Applied Mathematics\u00a054, 251\u2013266 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H. Whitney","year":"1932","unstructured":"Whitney, H.: Congruent graphs and the connectivity of graphs. American Journal of Mathematics\u00a054, 150\u2013168 (1932)","journal-title":"American Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11604686_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:04:32Z","timestamp":1619507072000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11604686_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540310006","9783540314684"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11604686_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}