{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:38:11Z","timestamp":1787495891243,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540590712","type":"print"},{"value":"9783540491835","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59071-4_41","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:02:55Z","timestamp":1330257775000},"page":"106-120","source":"Crossref","is-referenced-by-count":11,"title":["Dominoes"],"prefix":"10.1007","author":[{"given":"T.","family":"Kloks","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D.","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H.","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"9_CR1","first-page":"17","volume-title":"Beitr\u00e4ge zur Graphentheorie","author":"L. W. Beineke","year":"1968","unstructured":"Beineke, L. W., On derived graphs and digraphs, In: H. Sachs, H. J. Voss and H. Walther, eds., Beitr\u00e4ge zur Graphentheorie, Teubner, Leipzig, (1968), pp. 17\u201323."},{"key":"9_CR2","unstructured":"Berge, C., Hypergraphs, North Holland, 1989."},{"key":"9_CR3","first-page":"299","volume":"52","author":"J. C. Bermond","year":"1973","unstructured":"Bermond, J. C. and J. C. Meyer, Graphe repr\u00e9sentatif des ar\u00eates d'un multigraphe, J. Math. Pures Appl.\n52, (1973), pp. 299\u2013308.","journal-title":"J. Math. Pures Appl."},{"key":"9_CR4","first-page":"226","volume":"11","author":"H. L. Bodlaender","year":"1993","unstructured":"Bodlaender, H. L., A tourist guide through treewidth, Acta Cybernetica\n11, (1993), pp. 226\u2013234.","journal-title":"Acta Cybernetica"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0021-8693(76)90162-9","volume":"43","author":"P. J. Cameron","year":"1976","unstructured":"Cameron, P. J., J. M. Goethals, J. J. Seidel and E. E. Shult, Linegraphs, root systems and elliptic geometry, J. Algebra\n43, (1976), pp. 305\u2013327.","journal-title":"J. Algebra"},{"key":"9_CR6","first-page":"27","volume":"XXV","author":"P. Chaudhuri","year":"1987","unstructured":"Chaudhuri, P., An algorithm for finding all triangles in a digraph in parallel, Pure and Applied Mathematika Sciences, Vol. XXV, (1987), pp. 27\u201335.","journal-title":"Pure and Applied Mathematika Sciences"},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N. Chiba","year":"1985","unstructured":"Chiba, N. and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput.\n14, (1985), pp. 210\u2013223.","journal-title":"SIAM J. Comput."},{"key":"9_CR8","unstructured":"Biggs, N., Algebraic graph theory, Cambridge University Press, (1993)."},{"key":"9_CR9","volume-title":"Edge colorings of graphs","author":"S. Fiorini","year":"1977","unstructured":"Fiorini, S. and R. J. Wilson, Edge colorings of graphs, Pitman, London, (1977)."},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"Fulkerson, D. R. and O. A. Gross, Incidence matrices and interval graphs, Pacific J. Math.\n15, (1965), pp. 835\u2013855.","journal-title":"Pacific J. Math."},{"key":"9_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, (1980)."},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"1993","unstructured":"Gustedt, J., On the pathwidth of chordal graphs, Disc. Appl. Math.\n45, (1993), pp. 233\u2013248.","journal-title":"Disc. Appl. Math."},{"key":"9_CR13","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F., Graph Theory, Addison-Wesley Publ. Comp., Reading, Massachusetts, (1969)."},{"key":"9_CR14","first-page":"934","volume":"18","author":"R. L. Hemminger","year":"1971","unstructured":"Hemminger, R. L., Characterization of the line graph of a multigraph, Notices Amer. Math. Soc.\n18, (1971), pp. 934.","journal-title":"Notices Amer. Math. Soc."},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A. and M. Rodeh, Finding a minimal circuit in a graph, SIAM J. Comput.\n7, (1978), pp. 413\u2013423.","journal-title":"SIAM J. Comput."},{"key":"9_CR16","volume-title":"Ph.D. Thesis","author":"T. Kloks","year":"1993","unstructured":"Kloks, T., Treewidth, Ph.D. Thesis, Utrecht University, Utrecht, The Netherlands, 1993."},{"key":"9_CR17","first-page":"75","volume":"50","author":"J. Krausz","year":"1943","unstructured":"Krausz, J., D\u00e9monstration nouvelle d'un th\u00e9or\u00e8me de Whitney sur les r\u00e9saux, Mat. Fiz. Lapok\n50, (1943), pp. 75\u201385.","journal-title":"Mat. Fiz. Lapok"},{"key":"9_CR18","first-page":"527","volume-title":"Handbook of Theoretical Computer Science, A: Algorithms and Complexity","author":"J. Leeuwen van","year":"1990","unstructured":"Leeuwen, J. van, Graph Algorithms. In: J. van Leeuwen, ed., Handbook of Theoretical Computer Science, A: Algorithms and Complexity, Elsevier Science Publ., Amsterdam, 1990, pp. 527\u2013631."},{"key":"9_CR19","doi-asserted-by":"crossref","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, J. of the ACM\n21, (1974), pp. 569\u2013575.","journal-title":"J. of the ACM"},{"key":"9_CR20","unstructured":"Lov\u00e1sz, L. and M. D. Plummer, Matching Theory, Ann. Disc. Math. 29, (1986)."},{"key":"9_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(92)90028-V","volume":"55","author":"F. Maffray","year":"1992","unstructured":"Maffray, F., Kernels in perfect line-graphs, Journal of Combinatorial Theory, Series B\n55, (1992), pp. 1\u20138.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9_CR22","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G. J. Minty","year":"1980","unstructured":"Minty, G. J., On maximal independent sets of vertices in claw-free graphs, Journal on Combinatorial Theory, Series B\n28, (1980), pp. 284\u2013304.","journal-title":"Journal on Combinatorial Theory, Series B"},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B. and I. H. Sudborough, Min Cut is NP-complete for Edge Weighted Trees, Theoretical Computer Science\n58, (1988), pp. 209\u2013229.","journal-title":"Theoretical Computer Science"},{"key":"9_CR24","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N. D. Roussopoulos","year":"1973","unstructured":"Roussopoulos, N. D., A max{m, n} algorithm for determining the graph H from its line graph G, Information Processing Letters\n2, (1973), pp. 108\u2013112.","journal-title":"G, Information Processing Letters"},{"key":"9_CR25","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/0020-0190(82)90080-1","volume":"15","author":"M. M. Sys\u0142o","year":"1982","unstructured":"Sys\u0142o, M. M., A labeling algorithm to recognize a line digraph and output its root graph, Information Processing Letters\n15, (1982), pp. 28\u201330.","journal-title":"Information Processing Letters"},{"key":"9_CR26","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01593791","volume":"12","author":"L. E. Trotter","year":"1977","unstructured":"Trotter, L. E., Line perfect graphs, Mathematical Programming\n12, (1977), pp. 255\u2013259.","journal-title":"Mathematical Programming"}],"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\/3-540-59071-4_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:22:26Z","timestamp":1619558546000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59071-4_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590712","9783540491835"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-59071-4_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}