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

文章基本信息

  • 标题:Faster Exploration of Degree-Bounded Temporal Graphs
  • 本地全文:下载
  • 作者:Thomas Erlebach ; Jakob T. Spooner
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:117
  • 页码:1-13
  • DOI:10.4230/LIPIcs.MFCS.2018.36
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:A temporal graph can be viewed as a sequence of static graphs indexed by discrete time steps. The vertex set of each graph in the sequence remains the same; however, the edge sets are allowed to differ. A natural problem on temporal graphs is the Temporal Exploration problem (TEXP): given, as input, a temporal graph G of order n, we are tasked with computing an exploration schedule (i.e., a temporal walk that visits all vertices in G), such that the time step at which the walk arrives at the last unvisited vertex is minimised (we refer to this time step as the arrival time). It can be easily shown that general temporal graphs admit exploration schedules with arrival time no greater than O(n^2). Moreover, it has been shown previously that there exists an infinite family of temporal graphs for which any exploration schedule has arrival time Omega(n^2), making these bounds tight for general TEXP instances. We consider restricted instances of TEXP, in which the temporal graph given as input is, in every time step, of maximum degree d; we show an O(n^2/log n) bound on the arrival time when d is constant, and an O(d log d * n^2/log n) bound when d is given as some function of n.
  • 关键词:temporal graph exploration; algorithmic graph theory; NP-complete problem
国家哲学社会科学文献中心版权所有