IEICE TRANSACTIONS on Fundamentals
Twin Domination Problems in Round Digraphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1192-1199
- Publication Date
- 2014/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1192
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Tamaki NAKAJIMA
Gunma University
Yuuki TANAKA
Gunma University
Toru ARAKI
Gunma University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tamaki NAKAJIMA, Yuuki TANAKA, Toru ARAKI, "Twin Domination Problems in Round Digraphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1192-1199, June 2014, doi: 10.1587/transfun.E97.A.1192.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1192/_p
Copy
@ARTICLE{e97-a_6_1192,
author={Tamaki NAKAJIMA, Yuuki TANAKA, Toru ARAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Twin Domination Problems in Round Digraphs},
year={2014},
volume={E97-A},
number={6},
pages={1192-1199},
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.},
keywords={},
doi={10.1587/transfun.E97.A.1192},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Twin Domination Problems in Round Digraphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1192
EP - 1199
AU - Tamaki NAKAJIMA
AU - Yuuki TANAKA
AU - Toru ARAKI
PY - 2014
DO - 10.1587/transfun.E97.A.1192
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - 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.
ER -
English
