Two fixed-parameter algorithms for vertex covering by paths on trees

DOI10.1016/j.ipl.2007.10.007zbMath1185.05115MaRDI QIDQ963337

Rolf Niedermeier, Jiong Guo, Johannes Uhlmann

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.10.007

zbMATH Keywords

combinatorial problems; graph algorithms; fixed-parameter tractability; exact algorithms; vertex covering; ,covering trees by paths; weighted hitting set

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)