An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth

zbMath1464.05303arXiv1603.09448MaRDI QIDQ5207854

Yongtang Shi, Zongwen Bai, Jian-hua Tu

Publication date: 13 January 2020

Full work available at URL: https://arxiv.org/abs/1603.09448

zbMATH Keywords

dynamic programmingcombinatorial optimizationtreewidthvertex cover \(P_3\) problemconnected vertex cover \(P_3\) problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Unnamed Item ⋮ The maximum number of maximum dissociation sets in trees ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ General d-position sets