The temporal explorer who returns to the base
From MaRDI portal
Publication:5918316
DOI10.1016/j.jcss.2021.04.001OpenAlexW3155920611MaRDI QIDQ5918316
Eleni C. Akrida, Christoforos L. Raptopoulos, Paul G. Spirakis, George B. Mertzios
Publication date: 30 June 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.04713
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (5)
Untangling temporal graphs of bounded degree ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ Parameterised temporal exploration problems ⋮ Edge exploration of temporal graphs ⋮ Finding colorful paths in temporal graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Traveling salesman problems in temporal graphs
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- Computing maximal cliques in link streams
- Optimization, approximation, and complexity classes
- Discovering recurring activity in temporal networks
- On the approximability of an interval scheduling problem
- Temporal vertex cover with a sliding time window
- The complexity of optimal design of temporally connected graphs
- Temporal flows in temporal networks
- On temporal graph exploration
- Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks
- DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
- Dynamic Traveling Repair Problem with an Arbitrary Time Window
- Flooding Time of Edge-Markovian Evolving Graphs
- Exploration of Periodically Varying Graphs
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Fine-grained complexity analysis of two classic TSP variants
- Randomized Rumor Spreading in Dynamic Graphs
- A constant-factor approximation algorithm for the asymmetric traveling salesman problem
- Heuristic Approaches to Minimize Tour Duration for the TSP with Multiple Time Windows
- Temporal Network Optimization Subject to Connectivity Constraints
- An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Fast Convergence for Consensus in Dynamic Networks
- Connectivity and inference problems for temporal networks
This page was built for publication: The temporal explorer who returns to the base
