A note on the fine-grained complexity of MIS on regular graphs
type: Item
instance of: scholarly article
title: A note on the fine-grained complexity of MIS on regular graphs
author: Saeed Akhoondian Amiri
published in: Information Processing Letters
publication date: 2021-06-16T00:00:00Z
full work available at URL: https://arxiv.org/abs/2008.09008
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7360083
zbMATH Keywords: ETH
zbMATH Keywords: NP-complete
zbMATH Keywords: independent set
zbMATH Keywords: planar graphs
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
OpenAlex ID: W3153425020
cites work: Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
cites work: Fast algorithms for max independent set
cites work: A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
cites work: Q5501345
cites work: Maximum independent sets in 3- and 4-regular Hamiltonian graphs
cites work: A measure & conquer approach for the analysis of exact algorithms
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: Which problems have strongly exponential complexity?
cites work: Q4252414
cites work: Face covers and the genus problem for apex graphs
cites work: An improved exponential-time algorithm for k -SAT
cites work: Algorithms for maximum independent sets
cites work: Exact algorithms for maximum independent set
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1016/J.IPL.2021.106123
description: scientific article; zbMATH DE number 7360083