A refined algorithm for maximum independent set in degree-4 graphs
From MaRDI portal
Publication:1680494
DOI10.1007/s10878-017-0115-3zbMath1408.90267OpenAlexW2185104320MaRDI QIDQ1680494
Hiorshi Nagamochi, Mingyu Xiao
Publication date: 16 November 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-017-0115-3
Related Items (2)
Exact algorithms for maximum independent set ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4
Cites Work
- Unnamed Item
- Exact exponential algorithms.
- Improved upper bounds for 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
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Pathwidth of cubic graphs and exact algorithms
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Fast algorithms for max independent set
- Exact Algorithms for Maximum Independent Set
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs
- A measure & conquer approach for the analysis of exact algorithms
- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
- Maximum Independent Set in Graphs of Average Degree at Most Three in ${\mathcal O}(1.08537^n)$
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Algorithms for maximum independent sets
- Finding a Maximum Independent Set
- Further Improvement on Maximum Independent Set in Degree-4 Graphs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: A refined algorithm for maximum independent set in degree-4 graphs