VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On the minimum rainbow subgraph number of a graph
    Schiermeyer, Ingo
    We consider the Minimum Rainbow Subgraph problem (MRS): Given a graph ▫$G$▫, whose edges are coloured with ▫$p$▫ colours. Find a subgraph ▫$F \subseteq G$▫ of minimum order and with ▫$p$▫ edges such ... that each colour occurs exactly once. This problem is NP-hard and APX-hard. For a given graph ▫$G$▫ and an edge colouring ▫$c$▫ with ▫$p$▫ colours we define the rainbow subgraph number ▫$rs(G, c)$▫ to be the order of a minimum rainbow subgraph of ▫$G$▫ with size ▫$p$▫. In this paper we show lower and upper bounds for the rainbow subgraph number of a graph.
    Vir: Ars mathematica contemporanea : special issue Bled'11 (Vol. 6, no. 1, 2013, str. 83-88)
    Vrsta gradiva - prispevek na konferenci ; neleposlovje za odrasle
    Leto - 2013
    Jezik - angleški
    COBISS.SI-ID - 16470361

    Povezava(-e):

    http://amc.imfm.si/index.php/amc/article/view/246/187
    Digitalna knjižnica Slovenije - dLib.si

Vnos na polico