UP - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • On the embed and project algorithm for the graph bandwidth problem [Elektronski vir]
    Povh, Janez, 1973-
    The graph bandwidth problem, where one looks for a labeling of graph vertices that gives the minimum difference between the labels over all edges, is a classical NP-hard problem that has drawn a lot ... of attention in recent decades. In this paper, we focus on the so-called Embed and Project Algorithm (EPA) introduced by Blum et al. in 2000, which in the main part has to solve a semidefinite programming relaxation with exponentially many linear constraints. We present several theoretical properties of this special semidefinite programming problem (SDP) and a cutting-planelike algorithm to solve it, which works very efficiently in combination with interior-point methods or with the bundle method. Extensive numerical results demonstrate that this algorithm, which has only been studied theoretically so far, in practice gives very good labeling for graphs with n (less than or equal to) 1000.
    Vir: Mathematics [Elektronski vir]. - ISSN 2227-7390 (Vol. 9, iss. 17, Sep. 2021, str. 1-15)
    Vrsta gradiva - e-članek
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 74852611

    Povezava(-e):

    https://www.mdpi.com/2227-7390/9/17/2030
    Repozitorij Univerze v Ljubljani – RUL
    DOI

Vnos na polico