The search functionality is under construction.

Author Search Result

[Author] Shogo KAWARAGI(1hit)

1-1hit
  • Exact Exponential Algorithm for Distance-3 Independent Set Problem

    Katsuhisa YAMANAKA  Shogo KAWARAGI  Takashi HIRAYAMA  

     
    LETTER

      Pubricized:
    2018/10/30
      Vol:
    E102-D No:3
      Page(s):
    499-501

    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.