首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Two Moves per Time Step Make a Difference
  • 本地全文:下载
  • 作者:Thomas Erlebach ; Frank Kammer ; Kelin Luo
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:132
  • 页码:1-14
  • DOI:10.4230/LIPIcs.ICALP.2019.141
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.
  • 关键词:Temporal Graph Exploration; Algorithmic Graph Theory; NP-Complete Problem
国家哲学社会科学文献中心版权所有