University of Leicester
Browse

Non-Strict Temporal Exploration

Download (363.27 kB)
conference contribution
posted on 2020-07-21, 14:25 authored by Thomas Erlebach, Jakob T Spooner
A temporal graph G=〈G1,...,GL〉is a sequence of graphs Gi⊆G, for some given underlying graph G of order n. We consider the non-strict variant of the Temporal Exploration problem, in which we are asked to decide if G admits a sequence W of consecutively crossed edges e∈G, such that W visits all vertices at least once and that each e∈W is crossed at a timestep t′∈[L] such that t′≥t, where t is the time step during which the previous edge was crossed. This variant of the problem is shown to be NP-complete. We also consider the hardness of approximating the exploration time for yes-instances in which our order-ninput graph satisfies certain assumptions that ensure exploration schedules always exist. The first is that each pair of vertices are contained in the same component at least once in every period of nsteps, whilst the second is that the temporal diameter of our input graphis bounded by a constantc. For the latter of these two assumptions we showO(n12−ε)-inapproximability and O(n1−ε)-inapproximability in thec= 2 andc≥3 cases, respectively. For graphs with temporal diameterc= 2, we also prove an O(√nlogn) upper bound on worst-case time required for exploration, as well as anΩ(√n) lower bound

History

Source

27th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2020)

Version

  • AM (Accepted Manuscript)

Published in

Structural Information and Communication Complexity

Publisher

Springer Verlag

isbn

978-3-030-54921-3

Acceptance date

2020-05-05

Copyright date

2020

Available date

2020-10-24

Book series

Theoretical Computer Science and General Issues

Spatial coverage

Paderborn, Germany

Temporal coverage: start date

2020-06-29

Temporal coverage: end date

2020-07-01

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC