Professor Thomas Erlebach thomas.erlebach@durham.ac.uk
Professor Computer Science
Parameterized temporal exploration problems
Erlebach, Thomas; Spooner, Jakob T.
Authors
Jakob T. Spooner
Contributors
James Aspnes
Editor
Othon Michail
Editor
Abstract
In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph G admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices. Formally, a temporal graph is a sequence G = hG1, ..., GLi of graphs with V (Gt) = V (G) and E(Gt) ⊆ E(G) for all t ∈ [L] and some underlying graph G, and a temporal walk is a time-respecting sequence of edge-traversals. For the strict variant, in which edges must be traversed in strictly increasing timesteps, we give FPT algorithms for the problem of finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for the problem of finding a temporal walk that visits at least k distinct vertices in V , parameterized by k. For the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep, we parameterize by the lifetime L of the input graph and provide an FPT algorithm for the temporal exploration problem. We also give additional FPT or W[2]-hardness results for further problem variants.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) |
Start Date | Mar 28, 2022 |
End Date | Mar 30, 2022 |
Acceptance Date | Jan 31, 2022 |
Online Publication Date | Apr 29, 2022 |
Publication Date | 2022 |
Deposit Date | Feb 27, 2022 |
Publicly Available Date | May 11, 2022 |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Volume | 221 |
Pages | 15:1-15:17 |
Series Title | LIPIcs |
DOI | https://doi.org/10.4230/lipics.sand.2022.15 |
Public URL | https://durham-repository.worktribe.com/output/1137637 |
Files
Published Conference Proceeding
(889 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Thomas Erlebach and Jakob T. Spooner;
licensed under Creative Commons License CC-BY 4.0
You might also like
Sorting and Hypergraph Orientation under Uncertainty with Predictions
(2023)
Presentation / Conference Contribution
Package Delivery Using Drones with Restricted Movement Areas
(2022)
Presentation / Conference Contribution
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
(2022)
Presentation / Conference Contribution
Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty
(2021)
Presentation / Conference Contribution
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
(2021)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search