Above guarantee parameterization for vertex cover on graphs with maximum degree 4
From MaRDI portal
Publication:2111076
DOI10.1007/S10878-022-00966-8OpenAlexW2907957247MaRDI QIDQ2111076FDOQ2111076
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
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
- A refined algorithm for maximum independent set in degree-4 graphs
- LP can be a cure for parameterized problems
- The complexity of König subgraph problems and above-guarantee vertex cover
- Improved upper bounds for vertex cover
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Large Independent Sets in Triangle-Free Planar Graphs
- Vertex cover: Further observations and further improvements
- A Note on Vertex Cover in Graphs with Maximum Degree 3
- Faster Parameterized Algorithms Using Linear Programming
- Paths, Flowers and Vertex Cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Title not available (Why is that?)
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- Vertex Cover Gets Faster and Harder on Low Degree Graphs
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)
