Above guarantee parameterization for vertex cover on graphs with maximum degree 4

DOI10.1007/S10878-022-00966-8MaRDI QIDQ2111076OpenAlexFDO

Authors Dekel Tsur

Publication date 23 December 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsparameterized complexityvertex cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• An improved fixed-parameter algorithm for vertex cover
• A note on vertex cover in graphs with maximum degree 3
• scientific article; zbMATH DE number 1508265
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover

Cites work

• scientific article; zbMATH DE number 1508265 (Why is no real title available?)
• A note on vertex cover in graphs with maximum degree 3
• A refined algorithm for maximum independent set in degree-4 graphs
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Faster parameterized algorithms using linear programming
• Improved upper bounds for vertex cover
• LP can be a cure for parameterized problems
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• Large independent sets in triangle-free planar graphs
• Paths, flowers and vertex cover
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• The complexity of König subgraph problems and above-guarantee vertex cover
• Vertex Cover Gets Faster and Harder on Low Degree Graphs
• Vertex cover: Further observations and further improvements

Cited in

(2)

• Generalized above guarantee vertex cover and \(r\)-partization
• A note on vertex cover in graphs with maximum degree 3

This page was built for publication: Above guarantee parameterization for vertex cover on graphs with maximum degree 4

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