Concepedia

A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results

Journal of Computer and System Sciences · 2005 · 30 citations · 20 references

Concepts

ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational ComplexityGraph AlgorithmsGraph TheoryMatroid TheoryAlgorithmic Graph TheoryComputational Complexity Of AlgorithmsComputational Complexity Of Graph AlgorithmsEnumerative Graph TheoryGraph CompactionGraph CompressionGraph Enumeration

References

20

Graph Theory with Applications

E. Kay, J. A. Bondy, U. S. R. Murty · Operational Research Quarterly (1970-1977) · 1977 · 3K citations

Computing, Computer Science, Mathematics +12

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Tomás Feder, Moshe Y. Vardi · SIAM Journal on Computing · 1998 · 1.1K citations

Computing, Computer Science, Mathematics +15

On the complexity of H-coloring

Pavol Hell, Jaroslav Nešetřil · Journal of Combinatorial Theory Series B · 1990 · 671 citations

Computing, Computer Science, Mathematics +9

A graph coloring algorithm for large scheduling problems

Frank Thomson Leighton · Journal of Research of the National Bureau of Standards · 1979 · 492 citations · Full text

Computing, Computer Engineering, Computer Science +13

List Homomorphisms and Circular Arc Graphs

Tomás Feder, Pavol Hell, Jing Huang · COMBINATORICA · 1999 · 187 citations

Natural Sciences, Mathematics, Combinatorics +7