加载中…
2020-12-17
Hard Problems That Quickly Become Very Easy
Barnaby MartinDaniël PaulusmaSiani Smith
文献摘要
A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all graphs.
讨论
0讲解博客
生成讲解博客的中文版本
AI智能校验
生成AI智能校验的中文版本