The checkpoint problem
From MaRDI portal
Publication:714790
DOI10.1016/j.tcs.2012.05.021zbMath1252.68141MaRDI QIDQ714790
Julián Mestre, Guy Kortsarz, Rohit Khandekar, Mohammad Taghi Hajiaghayi
Publication date: 11 October 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.021
05C90: Applications of graph theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Evader interdiction: algorithms, complexity and collateral damage, On the minimum routing cost clustered tree problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On paths avoding forbidden pairs of vertices in a graph
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Partial multicuts in trees
- On the complexity of paths avoiding forbidden pairs
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Impossible pair constrained test path generation in a program
- Approximating directed multicuts
- On the hardness of approximating Multicut and Sparsest-Cut
- Proof verification and the hardness of approximation problems
- Combination Can Be Hard: Approximability of the Unique Coverage Problem
- Polynomial flow-cut gaps and hardness of directed cut problems
- Improved approximation for directed cut problems
- The importance of being biased
- Approximating the k-multicut problem
- The Traveling Salesman Problem with Distances One and Two
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- The complexity of satisfiability problems
- Finding Paths and Cycles of Superpolylogarithmic Length
- Greedy approximation algorithms for directed multicuts
- Computing and Combinatorics
- On the hardness of approximating spanners
