{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:46:03Z","timestamp":1725497163997},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_1","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"1-11","source":"Crossref","is-referenced-by-count":3,"title":["Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Petr","family":"Golovach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","series-title":"IMA Volumes in Mathematics and its Applications","first-page":"1","volume-title":"Sparse Matrix Computation: Graph Theory Issues and Algorithms","author":"J.R.S. Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique tree. In: George, J.A., Gilbert, J.R., Liu, J.W.H. (eds.) Sparse Matrix Computation: Graph Theory Issues and Algorithms. IMA Volumes in Mathematics and its Applications, vol.\u00a056, pp. 1\u201330. Springer, Heidelberg (1993)"},{"issue":"3","key":"1_CR2","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A.A. Bulatov","year":"2005","unstructured":"Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput.\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/jgt.10073","volume":"42","author":"T. Feder","year":"2003","unstructured":"Feder, T., Hell, P., Huang, J.: Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory\u00a042, 61\u201380 (2003)","journal-title":"Graph Theory"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"1","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of momotone monadic SNP and constraint satisfaction: A sudy through datalog and group theory. SIAM Journal of Computing\u00a01, 57\u2013104 (1998)","journal-title":"SIAM Journal of Computing"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/11917496_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Fiala","year":"2006","unstructured":"Fiala, J., Kratochvil, J.: Locally injective graph homomorphism: Lists guarantee dichotomy. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 15\u201326. Springer, Heidelberg (2006)"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2005.09.029","volume":"349","author":"J. Fiala","year":"2005","unstructured":"Fiala, J., Paulusma, D.: A complete complexity classification of the role assignment problem. Theoretical Computer Science 1\u00a0349, 67\u201381 (2005)","journal-title":"Theoretical Computer Science 1"},{"key":"1_CR7","volume-title":"Computers and intractability","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and intractability. W.H.Freeman, New York (1979)"},{"key":"1_CR8","volume-title":"Domination in Graphs: The Theory","author":"T. Haynes","year":"1997","unstructured":"Haynes, T., Hedetniemi, S., Slater, P.: Domination in Graphs: The Theory. Marcel Dekker, New York (1997)"},{"key":"1_CR9","first-page":"173","volume":"5","author":"P. Heggernes","year":"1998","unstructured":"Heggernes, P., Telle, J.A.: Partitioning graphs into generalized dominating sets. Nordic J. Comput.\u00a05, 173\u2013195 (1998)","journal-title":"Nordic J. Comput."},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-colouring. Journal of Combinatorial Theory B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory B"},{"key":"1_CR11","first-page":"41","volume":"2","author":"J. Kratochv\u00edl","year":"1995","unstructured":"Kratochv\u00edl, J., Manuel, P., Miller, M.: Generalized domination in chordal graphs. Nordic Journal of Computing\u00a02, 41\u201350 (1995)","journal-title":"Nordic Journal of Computing"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"A. Proskurowski","year":"1997","unstructured":"Proskurowski, A., Telle, J.A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math.\u00a010, 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR13","first-page":"216","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of the satisfability problem. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"1_CR14","first-page":"157","volume":"1","author":"J.A. Telle","year":"1994","unstructured":"Telle, J.A.: Complexity of domination-type problems in graphs. Nordic Journal of Computing\u00a01, 157\u2013171 (1994)","journal-title":"Nordic Journal of Computing"},{"key":"1_CR15","unstructured":"Telle, J.A.: Vertex partitioning problems: characterization, complexity and algorithms on partial k-trees, PhD tesisis, Department of Computer Science, Universiy of Oregon, Eugene (1994)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:42:28Z","timestamp":1619520148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_1","relation":{},"subject":[]}}