"Berlin" . . "Ukazujeme, \u017Ee pro ka\u017Ed\u00E9 \u010D\u00EDslo k je ot\u00E1zka existence (sigma,ro)-dominuj\u00EDc\u00ED mno\u017Einy v dan\u00E9m k=degenerovan\u00E9m grafu bu\u010F polynomi\u00E1ln\u00ED nebo NP-\u00FApln\u00E1, a pod\u00E1v\u00E1me \u00FAplnou charakterizaci t\u011Bchto p\u0159\u00EDpad\u016F pro kone\u010Dn\u00E9 mno\u017Einy sigma a ro."@cs . "Berlin" . "Generalized domination in degenerate graphs: A complete dichotomy of computational complexity" . "RIV/00216208:11320/08:00100095" . "000255239500016" . "Theory and Applications of Models of Computation, Proceedings" . . "369052" . "978-3-540-79227-7" . . "1"^^ . "[0D0A4D02D043]" . "We show that for every k, the problem of existence of a (sigma,rho)-dominating set performs a complete dichotomy when restricted to k-degenerate graphs, and we fully characterize the polynomial and NP-complete instances. It is further shown that the problem is polynomial time solvable if sigma, rho are such that every k-degenerate graph contains at most one (sigma, rho)-dominating set, and NP-complete otherwise. This relates to the concept of ambivalent graphs previously introduced for chordal graphs."@en . . . "Golovach, Petr" . "Generalized; domination; degenerate; graphs; complete; dichotomy; computational; complexity"@en . . "2"^^ . . . "Generalized domination in degenerate graphs: A complete dichotomy of computational complexity" . . . "We show that for every k, the problem of existence of a (sigma,rho)-dominating set performs a complete dichotomy when restricted to k-degenerate graphs, and we fully characterize the polynomial and NP-complete instances. It is further shown that the problem is polynomial time solvable if sigma, rho are such that every k-degenerate graph contains at most one (sigma, rho)-dominating set, and NP-complete otherwise. This relates to the concept of ambivalent graphs previously introduced for chordal graphs." . . "Zobecn\u011Bn\u00E1 dominace v degenerovan\u00FDch grafech: \u00DApln\u00E1 dichotomie v\u00FDpo\u010Detn\u00ED slo\u017Eitosti"@cs . . "2008-01-01+01:00"^^ . "P(1M0545), Z(MSM0021620838)" . . . "Kratochv\u00EDl, Jan" . "10"^^ . . . . "Generalized domination in degenerate graphs: A complete dichotomy of computational complexity"@en . . . "Generalized domination in degenerate graphs: A complete dichotomy of computational complexity"@en . . "Springer-Verlag" . . . "RIV/00216208:11320/08:00100095!RIV09-MSM-11320___" . "11320" . . "Zobecn\u011Bn\u00E1 dominace v degenerovan\u00FDch grafech: \u00DApln\u00E1 dichotomie v\u00FDpo\u010Detn\u00ED slo\u017Eitosti"@cs .