Parameterized algorithms for minimum sum vertex cover

DOI10.1016/J.TCS.2024.115032MaRDI QIDQ7033935zbMATH OpenFDO

Authors Shubhada Aute, Fahad Panolan

Publication date 3 February 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.115032

zbMATH Keywords

FPTinteger quadratic programmingvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Cites work

• A polynomial algorithm for the min-cut linear arrangement of trees
• A projected gradient algorithm for solving the maxcut SDP relaxation
• An improved deterministic algorithm for the online min-sum set cover problem
• Approximating min sum set cover
• Bandwidth parameterized by cluster vertex deletion number
• Complexity Results for Bandwidth Minimization
• Cutwidth I: A linear time fixed parameter algorithm
• Graph Layout Problems Parameterized by Vertex Cover
• Hardness results for approximating the bandwidth
• Improved approximations for min sum vertex cover and generalized min sum set cover
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• On chromatic sums and distributed resource allocation
• On optimal linear arrangements of trees
• Optimal Assignments of Numbers to Vertices
• Parameterized algorithmics for linear arrangement problems
• Parameterized complexity of bandwidth on trees
• Reducibility among combinatorial problems
• Results on the min-sum vertex cover problem
• Some results on approximability of minimum sum vertex cover
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The linear arrangement problem parameterized above guaranteed value
• The NP-completeness of the bandwidth minimization problem
• Topological Bandwidth
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(1)

• Solving SAT by restricted spiking neural P systems with temporal division rules

This page was built for publication: Parameterized algorithms for minimum sum vertex cover

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