VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Parameterized complexity of 1-planarity [Elektronski vir]
    Bannister, Michael J. ; Cabello, Sergio ; Eppstein, David
    We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known ... to be NP-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains NP-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
    Vir: Journal of graph algorithms and applications [Elektronski vir]. - ISSN 1526-1719 (Vol. 22, no. 1, 2018, str. 23-49)
    Vrsta gradiva - e-članek ; neleposlovje za odrasle
    Leto - 2018
    Jezik - angleški
    COBISS.SI-ID - 18208345

    Povezava(-e):

    http://dx.doi.org/10.7155/jgaa.00457
    DOI

Vnos na polico