An exact algorithm for maximum independent set in degree-5 graphs

DOI10.1016/j.dam.2014.07.009zbMath1326.05115OpenAlexW2047009939MaRDI QIDQ896662

Hiroshi Nagamochi, Mingyu Xiao

Publication date: 10 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.07.009

zbMATH Keywords

graph algorithmexact algorithmmaximum independent setmeasure and conqueramortized analysis

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Exact algorithms for maximum induced matching ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Exact algorithms for maximum independent set ⋮ An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses

Cites Work

• Unnamed Item
• Exact exponential algorithms.
• Improved upper bounds for 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
• A Note on Vertex Cover in Graphs with Maximum Degree 3
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: An exact algorithm for maximum independent set in degree-5 graphs