Hard problems that quickly become very easy

DOI10.1016/j.ipl.2021.106213OpenAlexW3206485671MaRDI QIDQ2059897

Daniël Paulusma, Siani Smith, Barnaby Martin

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.09770

zbMATH Keywords

computational complexityhereditary graph class\(H\)-free

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Finding matching cuts in \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Relationships between nondeterministic and deterministic tape complexities
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Colouring H-free graphs of bounded diameter.

This page was built for publication: Hard problems that quickly become very easy