Hard problems that quickly become very easy
type: Item
instance of: scholarly article
title: Hard problems that quickly become very easy
author: Barnaby Martin
author: Daniël Paulusma
author: Siani Smith
published in: Information Processing Letters
publication date: 2021-12-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/2012.09770
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7444827
zbMATH Keywords: computational complexity
zbMATH Keywords: hereditary graph class
zbMATH Keywords: \(H\)-free
MaRDI profile type: Publication
OpenAlex ID: W3206485671
cites work: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
cites work: A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
cites work: Q4083461
cites work: Colouring H-free graphs of bounded diameter.
cites work: Q4298260
cites work: Relationships between nondeterministic and deterministic tape complexities
DOI: 10.1016/J.IPL.2021.106213
description: scientific article; zbMATH DE number 7444827