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

DOI10.1007/s10878-022-00966-8OpenAlexW2907957247MaRDI QIDQ2111076

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 algorithmsvertex coverparameterized complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of König subgraph problems and above-guarantee vertex cover
• Improved upper bounds for vertex cover
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• Faster computation of maximum independent set and parameterized vertex cover for 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
• Vertex Cover: Further Observations and Further Improvements
• Vertex Cover Gets Faster and Harder on Low Degree Graphs
• Paths, Flowers and Vertex Cover
• A Note on Vertex Cover in Graphs with Maximum Degree 3
• Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
• Faster Parameterized Algorithms Using Linear Programming
• Large Independent Sets in Triangle-Free Planar Graphs

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