IEICE TRANSACTIONS on Information
Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds
Summary :
Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time is much faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.486-489
- Publication Date
- 2015/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2014FCP0007
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
- Category
Authors
Kazuyuki AMANO
Gunma University
Kyaw May OO
University of Computer Studies, Yangon
Yota OTACHI
Japan Advanced Institute of Science and Technology
Ryuhei UEHARA
Japan Advanced Institute of Science and Technology
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
Kazuyuki AMANO, Kyaw May OO, Yota OTACHI, Ryuhei UEHARA, "Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 3, pp. 486-489, March 2015, doi: 10.1587/transinf.2014FCP0007.
Abstract: Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time is much faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014FCP0007/_p
Copy
@ARTICLE{e98-d_3_486,
author={Kazuyuki AMANO, Kyaw May OO, Yota OTACHI, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds},
year={2015},
volume={E98-D},
number={3},
pages={486-489},
abstract={Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time is much faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.},
keywords={},
doi={10.1587/transinf.2014FCP0007},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds
T2 - IEICE TRANSACTIONS on Information
SP - 486
EP - 489
AU - Kazuyuki AMANO
AU - Kyaw May OO
AU - Yota OTACHI
AU - Ryuhei UEHARA
PY - 2015
DO - 10.1587/transinf.2014FCP0007
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time is much faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.
ER -
English
