DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
PDF
  • New models of graph-bin packing
    Bujtás, Csilla ...
    In Bujtás et al. [The graph-bin packing problem, Internat. J. Found. Comput. Sci. 22 (2011) 1971-1993.] the authors introduced a very general problem called Graph-Bin Packing (GBP). It requires a ... mapping ▫$\mu\: V(G) \rightarrow V(H)$▫ from the vertex set of an input graph ▫$G$▫ into a fixed host graph ▫$H$▫, which, among other conditions, satisfies that for each pair ▫$u,v$▫ of adjacent vertices the distance of ▫$\mu(u)$▫ and ▫$\mu(v)$▫ in ▫$H$▫ is between two prescribed bounds. In this paper we propose two online versions of the Graph-Bin Packing problem. In both cases the vertices can arrive in an arbitrary order where each new vertex is adjacent to some of the previous ones. One version is a Maker-Breaker game whose rules are defined by the packing conditions. A subclass of Maker-win input graphs is what we call `well-packable'; it means that a packing of ▫$G$▫ is obtained whenever the mapping ▫$\mu(u)$▫ is generated by selecting an arbitrary feasible vertex of the host graph for the next vertex of ▫$G$▫ in each step. The other model is connected-online packing where we are looking for an online algorithm which can always find a feasible packing. In both models we present some sufficient and some necessary conditions for packability. In the connected-online version we also give bounds on the size of used part of the host graph.
    Vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 640, Aug. 2016, str. 94-103)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2016
    Jezik - angleški
    COBISS.SI-ID - 18890329

    Povezava(-e):

    https://doi.org/10.1016/j.tcs.2016.06.008
    DOI

vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 640, Aug. 2016, str. 94-103)

loading ...
loading ...
loading ...

Vnos na polico