IEICE TRANSACTIONS on Information
Exact Exponential Algorithm for Distance-3 Independent Set Problem
Summary :
Let G=(V,E) be an unweighted simple graph. A distance-d independent set is a subset I ⊆ V such that dist(u, v) ≥ d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d ≥ 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143n) time.
- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.3 pp.499-501
- Publication Date
- 2019/03/01
- Publicized
- 2018/10/30
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018FCL0002
- Type of Manuscript
- Special Section LETTER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
- Category
Authors
Katsuhisa YAMANAKA
Iwate University
Shogo KAWARAGI
Iwate University
Takashi HIRAYAMA
Iwate 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
Katsuhisa YAMANAKA, Shogo KAWARAGI, Takashi HIRAYAMA, "Exact Exponential Algorithm for Distance-3 Independent Set Problem" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 3, pp. 499-501, March 2019, doi: 10.1587/transinf.2018FCL0002.
Abstract: Let G=(V,E) be an unweighted simple graph. A distance-d independent set is a subset I ⊆ V such that dist(u, v) ≥ d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d ≥ 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143n) time.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018FCL0002/_p
Copy
@ARTICLE{e102-d_3_499,
author={Katsuhisa YAMANAKA, Shogo KAWARAGI, Takashi HIRAYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={Exact Exponential Algorithm for Distance-3 Independent Set Problem},
year={2019},
volume={E102-D},
number={3},
pages={499-501},
abstract={Let G=(V,E) be an unweighted simple graph. A distance-d independent set is a subset I ⊆ V such that dist(u, v) ≥ d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d ≥ 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143n) time.},
keywords={},
doi={10.1587/transinf.2018FCL0002},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Exact Exponential Algorithm for Distance-3 Independent Set Problem
T2 - IEICE TRANSACTIONS on Information
SP - 499
EP - 501
AU - Katsuhisa YAMANAKA
AU - Shogo KAWARAGI
AU - Takashi HIRAYAMA
PY - 2019
DO - 10.1587/transinf.2018FCL0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2019
AB - Let G=(V,E) be an unweighted simple graph. A distance-d independent set is a subset I ⊆ V such that dist(u, v) ≥ d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d ≥ 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143n) time.
ER -
English
