Covering a tree with rooted subtrees -- parameterized and approximation algorithms

MaRDI QIDQ4608073zbMATH OpenFDO

Authors Lin Chen, Dániel Marx

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175482

zbMATH Keywords

integer programmingapproximation schemesschedulingfixed-parameter tractable

Mathematics Subject Classification ID

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)

Recommendations

• Exact and approximation algorithms for the min-max \(k\)-traveling salesmen problem on a tree
• A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
• Algorithms and Computation
• Packing and covering a tree by subtrees
• Min-max tree covers of graphs.

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
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
• 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
• A minimum-length covering subtree of a tree
• scientific article; zbMATH DE number 7758357 (Why is no real title available?)
• Evaluating and tuning \(n\)-fold integer programming
• scientific article; zbMATH DE number 7651172 (Why is no real title available?)
• Two fixed-parameter algorithms for vertex covering by paths on trees
• Block-structured integer programming: can we parameterize without the largest coefficient?
• Tight complexity lower bounds for integer linear programming with few constraints
• 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)