R. Sritharan

  1. Finding a sun in building-free graphs.

    Authors: Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad, R. Sritharan
    Subjects: Discrete Mathematics
    Abstract

    Deciding whether an arbitrary graph contains a sun was recently shown to be
    NP-complete. We show that whether a building-free graph contains a sun can be
    decided in O(min$\{m{n^3}, m^{1.5}n^2\}$) time and, if a sun exists, it can be
    found in the same time bound. The class of building-free graphs contains many
    interesting classes of perfect graphs such as Meyniel graphs which, in turn,
    contains classes such as hhd-free graphs, i-triangulated graphs, and parity
    graphs. Moreover, there are imperfect graphs that are building-free.

  2. On graphs without a C4 or a diamond.

    Authors: Elaine M. Eschen, Chinh T. Hoang, Jeremy P. Spinrad, R. Sritharan
    Subjects: Discrete Mathematics
    Abstract

    We consider the class of (C4, diamond)-free graphs; graphs in this class do
    not contain a C4 or a diamond as an induced subgraph. We provide an efficient
    recognition algorithm for this class. We count the number of maximal cliques in
    a (C4, diamond)-free graph and the number of n-vertex, labeled (C4,
    diamond)-free graphs. We also give an efficient algorithm for finding a largest
    clique in the more general class of (house, diamond)-free graphs.

RSS-материал