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
Cites Work
- Title not available (Why is that?)
- 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
- 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
Recommendations
- Title not available (Why is that?) 👍 👎
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3 👍 👎
- An improved fixed-parameter algorithm for vertex cover 👍 👎
- A Note on Vertex Cover in Graphs with Maximum Degree 3 👍 👎
- An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover} 👍 👎
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)
