VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • The complexity of obtaining a distance-balanced graph [Elektronski vir]
    Cabello, Sergio ; Lukšič, Primož, 1980-
    An unweighted, connected graph is distance-balanced (also called self-median) if there exists a number ▫$d$▫ such that, for any vertex ▫$v$▫, the sum of the distances from ▫$v$▫ to all other vertices ... is ▫$d$▫. An unweighted connected graphis strongly distance-balanced (also called distance-degree regular) if there exist numbers ▫$d_1, d_2, d_3,...$▫ such that, for any vertex ▫$v$▫, there are precisely ▫$d_k$▫ vertices at distance ▫$k$▫ from ▫$v$▫. We consider the following optimization problem: given a graph, add the minimum possible number of edges to obtain a (strongly) distance-balanced graph. We show that the problem is NP-hard for graphs of diameter three, thus answering the question posed by Jerebic et al. [Distance-balanced graphs; Ann. Comb. 2008]. In contrast, we show that the problem can be solved in polynomial time for graphs of diameter 2.
    Vir: Preprint series [Elektronski vir]. - ISSN 2232-2094 (Vol. 48, št. 1122, 2010, str. 1-9)
    Vrsta gradiva - e-članek
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 15631705

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/01122.pdf

Vnos na polico