article
NP for Combinatorialists
Gábor Kuna✉, Jaroslav Nešetřilb✉
- aDepartment of Mathematics, University of Memphis, 373 Dunn Hall, Memphis, TN 38152
- bDepartment of Applied Mathematics (KAM) and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám 22, Praha
- ✉Corresponding author
Looking for the full paper…
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
No abstract is available from our sources. Use “Read paper” to view it.
TL;DRIt is shown that every NP problem is polynomially equivalent to a simple combinatorial problem: the membership problem for a special class of digraphs, defined by means of shadows, and a surprising richness of coloring problems when restricted to most frequent graph classes is shown. (Semantic Scholar)