The search functionality is under construction.

Author Search Result

[Author] Ruka TANAHASHI(1hit)

1-1hit
  • A Deterministic Approximation Algorithm for Maximum 2-Path Packing

    Ruka TANAHASHI  Zhi-Zhong CHEN  

     
    PAPER

      Vol:
    E93-D No:2
      Page(s):
    241-249

    This paper deals with the maximum-weight 2-path packing problem (M2PP), which is the problem of computing a set of vertex-disjoint paths of length 2 in a given edge-weighted complete graph so that the total weight of edges in the paths is maximized. Previously, Hassin and Rubinstein gave a randomized cubic-time approximation algorithm for M2PP which achieves an expected ratio of - ε ≈ 0.5223 - ε for any constant ε > 0. We refine their algorithm and derandomize it to obtain a deterministic cubic-time approximation algorithm for the problem which achieves a better ratio (namely, 0.5265 - ε for any constant ε>0).