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

DOI10.1016/J.DAM.2014.07.009MaRDI QIDQ896662zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

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

exact algorithmgraph algorithmmeasure and conquermaximum independent setamortized analysis

Mathematics Subject Classification ID

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

Recommendations

• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• On maximum independent sets in \(P_{5}\)-free graphs
• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• An optimal maximal independent set algorithm for bounded-independence graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Exact algorithms for maximum independent set
• Exact Algorithms for Maximum Independent Set
• A refined algorithm for maximum independent set in degree-4 graphs
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• On the maximum independent set problem in graphs of bounded maximum degree

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• A fine-grained analysis of a simple independent set algorithm
• A measure \& conquer approach for the analysis of exact algorithms
• A note on vertex cover in graphs with maximum degree 3
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Algorithms for maximum independent sets
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Exact Algorithms for Maximum Independent Set
• Exact exponential algorithms.
• Fast algorithms for max independent set
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Finding a Maximum Independent Set
• Graph-Theoretic Concepts in Computer Science
• Improved upper bounds for vertex cover
• Pathwidth of cubic graphs and exact algorithms
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms

Cited in

(10)

• Exact algorithms for maximum induced matching
• Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
• An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Algorithm to find a maximum 2-packing set in a cactus
• A randomized algorithm for determining dominating sets in graphs of maximum degree five
• scientific article; zbMATH DE number 861311 (Why is no real title available?)
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• Exact algorithms for maximum independent set
• A refined algorithm for maximum independent set in degree-4 graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896662)