Nothing Special   »   [go: up one dir, main page]

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Online ISSN : 1745-1337
Print ISSN : 0916-8508
Special Section on Discrete Mathematics and Its Applications
Twin Domination Problems in Round Digraphs
Tamaki NAKAJIMAYuuki TANAKAToru ARAKI
Author information
JOURNAL RESTRICTED ACCESS

2014 Volume E97.A Issue 6 Pages 1192-1199

Details
Abstract

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.

Content from these authors
© 2014 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top