DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
PDF
  • On caterpillar factors in graphs
    Bujtás, Csilla ; Jendrol', Stanislav ; Tuza, Zsolt
    A caterpillar is either a ▫$K_2$▫ or a tree on at least 3 vertices such that deleting its leaves we obtain a path of order at least 1. Given a simple undirected graph ▫$G = (V , E)$▫, a caterpillar ... factor of ▫$G$▫ is a set of caterpillar subgraphs of ▫$G$▫ such that each vertex ▫$v\in V$▫ belongs to exactly one of them. A caterpillar factor ▫$F$▫ is internally even if every vertex of degree ▫$\deg_F(v)\geq 2$▫ has an even degree; ▫$F$▫ is odd if ▫$\deg_F(v)$▫ is odd for every ▫$v\in V(G)$▫. We present a linear-time algorithm that decides whether a tree admits an internally even caterpillar factor and, on the other hand, we prove that the decision problem is NP-complete on the class of planar bipartite graphs. For the odd caterpillar factor problem, we obtain similar results. It can be decided in linear time over the class of trees, but the problem is NP-complete on the class of bipartite graphs.
    Vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 846, Dec. 2020, str. 82-90)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2020
    Jezik - angleški
    COBISS.SI-ID - 117212419

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0304397520305156
    DOI

vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 846, Dec. 2020, str. 82-90)

loading ...
loading ...
loading ...

Vnos na polico