Above guarantee parameterization for vertex cover on graphs with maximum degree 4
type: Item
instance of: scholarly article
title: Above guarantee parameterization for vertex cover on graphs with maximum degree 4
author: Dekel Tsur
published in: Journal of Combinatorial Optimization
publication date: 2022-12-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1812.10808
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 7636975
zbMATH Keywords: vertex cover
zbMATH Keywords: graph algorithms
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
OpenAlex ID: W2907957247
cites work: Vertex Cover Gets Faster and Harder on Low Degree Graphs
cites work: Q4506265
cites work: Vertex cover: Further observations and further improvements
cites work: Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
cites work: Improved upper bounds for vertex cover
cites work: Large Independent Sets in Triangle-Free Planar Graphs
cites work: Faster Parameterized Algorithms Using Linear Programming
cites work: Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
cites work: The complexity of König subgraph problems and above-guarantee vertex cover
cites work: LP can be a cure for parameterized problems
cites work: Paths, Flowers and Vertex Cover
cites work: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
cites work: A Note on Vertex Cover in Graphs with Maximum Degree 3
cites work: A refined algorithm for maximum independent set in degree-4 graphs
cites work: Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
DOI: 10.1007/S10878-022-00966-8
description: scientific article; zbMATH DE number 7636975