DIKUL - logo
(UL)
  • Recognizing ▫$k$▫-equistable graphs in FPT time
    Kim, Eun Jung ; Milanič, Martin, 1980- ; Schaudt, Oliver
    A graph ▫$G = (V,E)$▫ is called equistable if there exist a positive integer ▫$t$▫ and a weight function ▫$w : V \to \mathbb{N}$▫ such that ▫$S \subseteq V$▫ is a maximal stable set of ▫$G$▫ if and ... only if ▫$w(S) = t$▫. Such a function ▫$w$▫ is called an equistable function of ▫$G$▫. For a positive integer ▫$k$▫, a graph ▫$G = (V,E)$▫ is said to be ▫$k$▫-equistable if it admits an equistable function which is bounded by ▫$k$▫. We prove that the problem of recognizing ▫$k$▫-equistable graphs is fixed parameter tractable when parameterized by ▫$k$▫, affirmatively answering a question of Levit et al. In fact, the problem admits an ▫$O(k^5)$▫-vertex kernel that can be computed in linear time.
    Vir: Graph-theoretic concepts in computer science : 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015, : revised papers (Str. 487-498)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2016
    Jezik - angleški
    COBISS.SI-ID - 1539019460

    Povezava(-e):

    http://dx.doi.org/10.1007/978-3-662-53174-7_34

Vnos na polico