. "P(1M0545), Z(MSM0021620838)" . "[08B898CF66B1]" . . "Computational; complexity; generalized; domination; complete; dichotomy; chordal; graphs"@en . "Golovach, Petr" . "Berlin" . . "Berlin" . "RIV/00216208:11320/07:00206159!RIV10-MSM-11320___" . . . "We show that for chordal graphs, the problem of deciding the existence of a ($\\sigma,\\rho$)-dominating set performs a complete dichotomy: it is polynomial time solvable if $\\sigma, \\rho$ are such that every chordal graph contains at most one $(\\sigma,\\rho)$-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs $(\\sigma,\\rho)$ by a structural description, but at least we can provide a recursive algorithm for their recognition."@en . "978-3-540-74838-0" . . . . . . . "000252884200001" . . "Springer-Verlag" . "2"^^ . . "Computational complexity of generalized domination: A complete dichotomy for chordal graphs"@en . . "Computational complexity of generalized domination: A complete dichotomy for chordal graphs"@en . "2007-01-01+01:00"^^ . "We show that for chordal graphs, the problem of deciding the existence of a ($\\sigma,\\rho$)-dominating set performs a complete dichotomy: it is polynomial time solvable if $\\sigma, \\rho$ are such that every chordal graph contains at most one $(\\sigma,\\rho)$-dominating set, and NP-complete otherwise. The proof involves certain flavor of existentionality - we are not able to characterize such pairs $(\\sigma,\\rho)$ by a structural description, but at least we can provide a recursive algorithm for their recognition." . . "RIV/00216208:11320/07:00206159" . "11320" . . "1"^^ . . "414598" . "Kratochv\u00EDl, Jan" . "Computational complexity of generalized domination: A complete dichotomy for chordal graphs" . . . . . "11"^^ . . . "Computational complexity of generalized domination: A complete dichotomy for chordal graphs" . "Graph-theoretic Concepts in Computer Science" .