グラフ上のラベル付きトークン整列問題 Swapping Labeled Tokens on Graphs (Theoretical Foundations of Computing)

Search this Article

Author(s)

Abstract

連結なグラフの頂点上に配置されたトークンを指定された頂点に移動するパズルを考える.グラフはn個の頂点をもち,トークンもn個存在する.各トークンは,互いに異なる頂点に配置され,互いに異なる頂点が目的地として指定されている.隣接する頂点に配置されている2つのトークンを交換することを繰り返して,全てのトークンを目的の頂点へ移動させたい.はじめに本稿では,トークンの交換をO(n^2)回だけ行えば,どんな入力に対してもこのパズルが解けることを示す.したがって,次に本稿では,トークンの最小交換回数に焦点をあてて議論していく.まず,木に対して,多項式時間2倍近似アルゴリズムを与える.次に,このアルゴリズムを用いて,グラフのtreeα-spannerが多項式時間で計算できるという仮定のもとで多項式時間2α倍近似アルゴリズムを示す.最後に,完全2部グラフに対して,トークンの最小交換回数を厳密に計算する多項式時間アルゴリズムを与える.

Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n^2) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 114(19), 5-12, 2014-04-24

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    110009875043
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • ISSN
    0913-5685
  • NDL Article ID
    025446604
  • NDL Call No.
    Z16-940
  • Data Source
    NDL  NII-ELS 
Page Top