Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
From MaRDI portal
Publication:1026228
DOI10.1016/j.jda.2008.09.004zbMath1187.68353OpenAlexW1994773828MaRDI QIDQ1026228
Publication date: 24 June 2009
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2008.09.004
Related Items (13)
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ On bipartization of cubic graphs by removal of an independent set ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A multivariate framework for weighted FPT algorithms ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ Fast algorithms for max independent set ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Exact algorithms for maximum independent set ⋮ 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Pathwidth of cubic graphs and exact algorithms
- Vertex Cover: Further Observations and Further Improvements
- An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
- A new approach to proving upper bounds for MAX-2-SAT
This page was built for publication: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
