Algorithm for online 3-path vertex cover

DOI10.1007/S00224-019-09944-WMaRDI QIDQ2300630zbMATH OpenOpenAlexWikidataFDO

Authors Yubai Zhang, Zhao Zhang, Yishuo Shi, Xianyue Li

Publication date 27 February 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-019-09944-w

zbMATH Keywords

3-path vertex coveronline algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Recommendations

• Parameterized algorithm for 3-path vertex cover
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• A faster FPT algorithm for 3-path vertex cover
• Approximation algorithm for minimum connected 3-path vertex cover
• Kernelization of the 3-path vertex cover problem

Cites work

• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A faster FPT algorithm for 3-path vertex cover
• A fixed-parameter algorithm for the vertex cover P₃ problem
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• A unified approximation algorithm for node-deletion problems
• Approximation and online algorithms for multidimensional bin packing: a survey
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Mean analysis of an online algorithm for the vertex cover problem
• Minimum \(k\)-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the vertex cover \(P_3\) problem parameterized by treewidth
• On the weighted \(k\)-path vertex cover problem
• On-line vertex-covering
• Online algorithms. The state of the art
• Online algorithms: a survey
• The vertex cover \(P_3\) problem in cubic graphs

Cited in

(2)

• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• Delaying decisions and reservation costs

This page was built for publication: Algorithm for online 3-path vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300630)