VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Crossing number and weighted crossing number of near-planar graphs
    Cabello, Sergio ; Mohar, Bojan, 1956-
    A nonplanar graph ▫$G$▫ is near-planar if it contains an edge ▫$e$▫ such that ▫$G-e$▫ is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different ... combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněný and Salazar (Graph Drawing GD'06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs.
    Vir: Algorithmica. - ISSN 0178-4617 (Vol. 60, no. 3, 2011, str. 484-504)
    Vrsta gradiva - članek, sestavni del
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 15261785

    Povezava(-e):

    http://dx.doi.org/10.1007/s00453-009-9357-5

vir: Algorithmica. - ISSN 0178-4617 (Vol. 60, no. 3, 2011, str. 484-504)
loading ...
loading ...
loading ...

Vnos na polico