Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds

Kazuyuki AMANO; Kyaw May OO; Yota OTACHI; Ryuhei UEHARA

doi:10.1587/transinf.2014FCP0007

Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds

Kazuyuki AMANO, Kyaw May OO, Yota OTACHI, Ryuhei UEHARA

Full Text Views

0

Share
Cite this

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

secure set, defensive alliance, fixed-parameter tractability, hypercube

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://globals.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 -