Traveling salesman problems in temporal graphs
From MaRDI portal
Publication:284573
DOI10.1016/j.tcs.2016.04.006zbMath1338.90349OpenAlexW2330664568MaRDI QIDQ284573
Othon Michail, Paul G. Spirakis
Publication date: 18 May 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.006
approximation algorithmdynamic networkexplorationhardness resulttemporal matchingTSP with costs one and two
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (35)
On exploring always-connected temporal graphs of small pathwidth ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ Exploring a dynamic ring without landmark ⋮ The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable ⋮ On temporal graph exploration ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Distributed exploration of dynamic rings ⋮ A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Non-strict Temporal Exploration ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Disentangling the computational complexity of network untangling ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Eulerian walks in temporal graphs ⋮ Unnamed Item ⋮ Parameterised temporal exploration problems ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ On short fastest paths in temporal graphs ⋮ Temporal Vertex Cover with a Sliding Time Window ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ Exploration of \(k\)-edge-deficient temporal graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ Temporal vertex cover with a sliding time window ⋮ Temporal graph classes: a view through temporal separators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring ⋮ Temporal matching ⋮ Exploration of dynamic cactuses with sub-logarithmic overhead ⋮ Sliding window temporal graph coloring ⋮ The temporal explorer who returns to the base ⋮ Edge exploration of temporal graphs ⋮ Königsberg sightseeing: Eulerian walks in temporal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Mediated population protocols
- Shortest paths without a map
- Causality, influence, and computation in possibly disconnected synchronous dynamic networks
- The labeled perfect matching in bipartite graphs
- Efficient continuous-time dynamic network flow algorithms
- On the minimum label spanning tree problem
- Derandomized graph products
- Computation in networks of passively mobile finite-state sensors
- New Inapproximability Bounds for TSP
- Distributed computation in dynamic networks
- Traveling Salesman Problems in Temporal Graphs
- Flooding time in edge-Markovian dynamic graphs
- An Introduction to Temporal Graphs: An Algorithmic Perspective
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- 8/7-approximation algorithm for (1,2)-TSP
- On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
- Some Matching Problems for Bipartite Graphs
- Spanning trees with many or few colors in edge-colored graphs
- The Traveling Salesman Problem with Distances One and Two
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Temporal Network Optimization Subject to Connectivity Constraints
- Paths, Trees, and Flowers
- The complexity of satisfiability problems
- A Randomized Rounding Approach to the Traveling Salesman Problem
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- On the Complexity of Information Spreading in Dynamic Networks
- Simple and efficient local codes for distributed stable network construction
- Connectivity and inference problems for temporal networks
- Graph colouring and the probabilistic method
This page was built for publication: Traveling salesman problems in temporal graphs
