Covering a tree with rooted subtrees -- parameterized and approximation algorithms
From MaRDI portal
Publication:4608073
zbMATH Open1403.68343MaRDI QIDQ4608073FDOQ4608073
Authors: Lin Chen, Dániel Marx
Publication date: 15 March 2018
Full work available at URL: http://dl.acm.org/citation.cfm?id=3175482
Recommendations
Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Integer programming (90C10)
Cited In (24)
- Extremal cover cost and reverse cover cost of trees with given segment sequence
- Trees with the mos subtrees - an algorithmic approach
- Approximating the minmax rooted-tree cover in a tree
- Optimal direct and indirect covering trees
- High-multiplicity \(N\)-fold IP via configuration LP
- Integer programming in parameterized complexity: three miniatures
- A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
- Minmax subtree cover problem on cacti
- Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
- FPT algorithms for a special block-structured integer program with applications in scheduling
- Subset selection in sparse matrices
- Mixed covering of trees and the augmentation problem with odd diameter constraints
- Integer programming in parameterized complexity: five miniatures
- Title not available (Why is that?)
- A minimum-length covering subtree of a tree
- Evaluating and tuning \(n\)-fold integer programming
- Title not available (Why is that?)
- Block-structured integer programming: can we parameterize without the largest coefficient?
- Tight complexity lower bounds for integer linear programming with few constraints
- Two fixed-parameter algorithms for vertex covering by paths on trees
- Faster Algorithms for Integer Programs with Block Structure
- Exact approaches for solving a covering problem with capacitated subtrees
This page was built for publication: Covering a tree with rooted subtrees -- parameterized and approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608073)