A refined algorithm for maximum independent set in degree-4 graphs

DOI10.1007/S10878-017-0115-3MaRDI QIDQ1680494zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiorshi Nagamochi

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

zbMATH Keywords

exact algorithmsgraph algorithmsmeasure-and-conquermaximum independent setamortized analysis

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• An exact algorithm for maximum independent set in degree-5 graphs
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Exact algorithms for maximum independent set

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 simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• Algorithms for maximum independent sets
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• 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
• 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
• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• Graph-Theoretic Concepts in Computer Science
• Improved upper bounds for vertex cover
• Maximum Independent Set in graphs of average degree at most three in \({\mathcal O}(1.08537^n)\)
• Pathwidth of cubic graphs and exact algorithms
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms

Cited in

(8)

• Further Improvement on Maximum Independent Set in Degree-4 Graphs
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• An exact algorithm for maximum independent set in degree-5 graphs
• An improved exact algorithm for TSP in graphs of maximum degree 4
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• Exact algorithms for maximum independent set

This page was built for publication: A refined algorithm for maximum independent set in degree-4 graphs

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