Traveling salesman problems in temporal graphs
From MaRDI portal
Publication:284573
DOI10.1016/J.TCS.2016.04.006zbMATH Open1338.90349OpenAlexW2330664568MaRDI QIDQ284573FDOQ284573
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
Recommendations
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)
Cites Work
- Paths, Trees, and Flowers
- Computation in networks of passively mobile finite-state sensors
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of satisfiability problems
- Flooding time in edge-Markovian dynamic graphs
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Graph colouring and the probabilistic method
- The labeled perfect matching in bipartite graphs
- Efficient continuous-time dynamic network flow algorithms
- On the minimum label spanning tree problem
- Derandomized graph products
- Title not available (Why is that?)
- New Inapproximability Bounds for TSP
- Distributed computation in dynamic networks
- Traveling Salesman Problems in Temporal Graphs
- An Introduction to Temporal Graphs: An Algorithmic Perspective
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Temporal Network Optimization Subject to Connectivity Constraints
- Mediated population protocols
- Title not available (Why is that?)
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Title not available (Why is that?)
- 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
- Shortest paths without a map
- Causality, influence, and computation in possibly disconnected synchronous dynamic networks
Cited In (39)
- Temporal graph classes: a view through temporal separators
- A cop and robber game on edge-periodic temporal graphs
- Disentangling the computational complexity of network untangling
- A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs
- Deleting edges to restrict the size of an epidemic in temporal networks
- Temporal vertex cover with a sliding time window
- On short fastest paths in temporal graphs
- Sliding window temporal graph coloring
- An LP-based approximation algorithm for the generalized traveling salesman path problem
- On exploring always-connected temporal graphs of small pathwidth
- Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring
- Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs
- Temporal Traveling Salesman Problem – in a Logic- and Graph Theory-Based Depiction
- Exploring a Dynamic Ring Without Landmark
- Temporal matching
- The complexity of computing optimum labelings for temporal connectivity
- Exploration of dynamic cactuses with sub-logarithmic overhead
- Exploration of \(k\)-edge-deficient temporal graphs
- Distributed exploration of dynamic rings
- Efficient live exploration of a dynamic ring with mobile robots
- The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
- Exploration of \(k\)-edge-deficient temporal graphs
- Edge exploration of temporal graphs
- Exploring a dynamic ring without landmark
- The temporal explorer who returns to the base
- Exploration of dynamic networks: tight bounds on the number of agents
- Title not available (Why is that?)
- Maximum 0-1 timed matching on temporal graphs
- Title not available (Why is that?)
- Non-strict Temporal Exploration
- On temporal graph exploration
- Königsberg sightseeing: Eulerian walks in temporal graphs
- Eulerian walks in temporal graphs
- Temporal Vertex Cover with a Sliding Time Window
- The Complexity of Finding Small Separators in Temporal Graphs
- Optimizing reachability sets in temporal graphs by delaying
- Title not available (Why is that?)
- Parameterised temporal exploration problems
- The complexity of finding small separators in temporal graphs
This page was built for publication: Traveling salesman problems in temporal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284573)
