The checkpoint problem
From MaRDI portal
Publication:714790
DOI10.1016/j.tcs.2012.05.021zbMath1252.68141OpenAlexW2002766600MaRDI 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
Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
On the minimum routing cost clustered tree problem ⋮ Evader interdiction: algorithms, complexity and collateral damage
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
This page was built for publication: The checkpoint problem
