Parameterised temporal exploration problems

DOI10.1016/J.JCSS.2023.01.003MaRDI QIDQ2698289zbMATH OpenOpenAlexFDO

Authors Jakob T. Spooner, Thomas Erlebach

Publication date 21 April 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2212.01594

zbMATH Keywords

fixed-parameter tractabilityparameterised complexitytemporal graphs

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Non-strict Temporal Exploration
• Finding Temporal Paths Under Waiting Time Constraints.
• Finding temporal paths under waiting time constraints
• The complexity of temporal constraint satisfaction problems
• Discrete temporal constraint satisfaction problems
• Publication:5750422
• Temporal constraints: A survey
• Faster exploration of degree-bounded temporal graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 727573 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A Remark on Stirling's Formula
• An introduction to temporal graphs: an algorithmic perspective
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Color-coding
• Computing maximum matchings in temporal graphs.
• Connectivity and inference problems for temporal networks
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Exploration of the T-interval-connected dynamic graphs: the case of the ring
• Finding temporal paths under waiting time constraints
• Non-strict Temporal Exploration
• On exploring always-connected temporal graphs of small pathwidth
• Online and offline algorithms for the time-dependent TSP with time zones
• Parameterized algorithms
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• The temporal explorer who returns to the base
• Traveling salesman problems in temporal graphs
• Two moves per time step make a difference

Cited in

(1)

• Collision-free robot scheduling

This page was built for publication: Parameterised temporal exploration problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2698289)