The search functionality is under construction.

Author Search Result

[Author] Tamaki NAKAJIMA(1hit)

1-1hit
  • Twin Domination Problems in Round Digraphs

    Tamaki NAKAJIMA  Yuuki TANAKA  Toru ARAKI  

     
    PAPER

      Vol:
    E97-A No:6
      Page(s):
    1192-1199

    A twin dominating set of a digraph D is a subset S of vertices if, for every vertex u ∉ S, there are vertices x,y ∈ S such that ux and yu are arcs of D. A digraph D is round if the vertices can be labeled as v0,v1,...,vn-1 so that, for each vertex vi, the out-neighbors of vi appear consecutively following vi and the in-neighbors of vi appear consecutively preceding vi. In this paper, we give polynomial time algorithms for finding a minimum weight twin dominating set and a minimum weight total twin dominating set for a weighted round digraph. Then we show that there is a polynomial time algorithm for deciding whether a locally semicomplete digraph has an independent twin dominating set. The class of locally semicomplete digraphs contains round digraphs as a special case.