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

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

• 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.

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)

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)